Task: | Fragile network |
Sender: | aalto2024g_006 |
Submission time: | 2024-10-09 16:48:34 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | ACCEPTED | 0.16 s | details |
#7 | ACCEPTED | 0.09 s | details |
#8 | ACCEPTED | 0.14 s | details |
#9 | ACCEPTED | 0.09 s | details |
#10 | ACCEPTED | 0.09 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
#13 | WRONG ANSWER | 0.00 s | details |
#14 | WRONG ANSWER | 0.08 s | details |
#15 | WRONG ANSWER | 0.00 s | details |
#16 | WRONG ANSWER | 0.00 s | details |
#17 | WRONG ANSWER | 0.00 s | details |
#18 | WRONG ANSWER | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | WRONG ANSWER | 0.00 s | details |
#21 | ACCEPTED | 0.00 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 49 | for (int i = 0; i < p.size(); i++) { | ~~^~~~~~~~~~
Code
#include <algorithm> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n; cin >> n; vector<vector<int>> g(n + 1); vector<pair<int, int>> p; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } queue<int> critical; queue<int> normal; for (int i = 1; i <= n; i++) { vector<int> adj = g[i]; if (adj.size() <= 1) critical.push(i); else normal.push(i); } while (!critical.empty()) { int crrnt = critical.front(); critical.pop(); if (!critical.empty()) { int conn = critical.front(); critical.pop(); g[crrnt].push_back(conn); g[conn].push_back(crrnt); p.push_back({crrnt, conn}); } else { int conn = normal.front(); normal.push(crrnt); g[crrnt].push_back(conn); g[conn].push_back(crrnt); p.push_back({crrnt, conn}); } } cout << p.size() << endl; for (int i = 0; i < p.size(); i++) { cout << p[i].first << ' ' << p[i].second << endl; } // vector<vector<pair<int, int> > > path(n, vector<pair<int, int> >(m)); }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 1 5 1 7 1 8 1 3 ... |
correct output |
---|
5 5 2 7 9 8 6 3 10 ... |
user output |
---|
5 2 3 4 5 6 7 8 9 ... |
Test 2
Verdict: ACCEPTED
input |
---|
10 4 5 3 4 2 3 9 10 ... |
correct output |
---|
1 10 1 |
user output |
---|
1 1 10 |
Test 3
Verdict: ACCEPTED
input |
---|
10 1 8 1 3 3 5 5 7 ... |
correct output |
---|
3 7 10 8 2 1 9 |
user output |
---|
3 2 7 8 9 10 1 |
Test 4
Verdict: ACCEPTED
input |
---|
10 1 5 3 7 2 10 3 8 ... |
correct output |
---|
3 10 8 6 4 5 9 |
user output |
---|
3 4 5 6 8 9 10 |
Test 5
Verdict: WRONG ANSWER
input |
---|
10 4 8 3 4 4 6 2 3 ... |
correct output |
---|
3 8 7 10 9 1 6 |
user output |
---|
3 6 7 8 9 10 1 |
Test 6
Verdict: ACCEPTED
input |
---|
100000 1 56967 1 56618 1 42321 1 82550 ... |
correct output |
---|
50000 56967 16911 56618 39942 42321 99902 82550 2538 ... |
user output |
---|
50000 2 3 4 5 6 7 8 9 ... Truncated |
Test 7
Verdict: ACCEPTED
input |
---|
100000 92297 92298 23511 23512 68057 68058 65434 65435 ... |
correct output |
---|
1 100000 1 |
user output |
---|
1 1 100000 |
Test 8
Verdict: ACCEPTED
input |
---|
100000 17747 97512 10397 12053 679 6975 4013 14565 ... |
correct output |
---|
25057 92881 76094 20353 87429 16069 96487 71186 52809 ... |
user output |
---|
25057 388 577 715 785 837 1166 1220 1261 ... Truncated |
Test 9
Verdict: ACCEPTED
input |
---|
100000 72941 72942 11232 11233 73464 73465 30042 30043 ... |
correct output |
---|
489 16423 85168 20707 94190 36505 54940 96411 44067 ... |
user output |
---|
489 1 99 667 718 884 1400 1404 1453 ... Truncated |
Test 10
Verdict: ACCEPTED
input |
---|
100000 31451 31452 7473 7474 24056 24057 85181 85182 ... |
correct output |
---|
51 25638 2983 87594 87371 92001 50610 46744 100000 ... |
user output |
---|
51 1 140 346 1093 2983 5134 6092 6887 ... Truncated |
Test 11
Verdict: ACCEPTED
input |
---|
10 1 2 1 3 3 4 3 5 ... |
correct output |
---|
2 2 6 4 10 |
user output |
---|
2 2 4 6 10 |
Test 12
Verdict: WRONG ANSWER
input |
---|
7 1 2 2 3 2 4 1 5 ... |
correct output |
---|
2 4 7 3 6 |
user output |
---|
2 3 4 6 7 |
Test 13
Verdict: WRONG ANSWER
input |
---|
6 1 2 1 3 1 4 4 5 ... |
correct output |
---|
2 3 6 2 5 |
user output |
---|
2 2 3 5 6 |
Test 14
Verdict: WRONG ANSWER
input |
---|
65538 1 2 1 3 1 4 3 5 ... |
correct output |
---|
16385 34 36 40 42 35 41 48 50 ... |
user output |
---|
16385 2 4 33 34 35 36 39 40 ... Truncated |
Test 15
Verdict: WRONG ANSWER
input |
---|
11 1 2 1 3 2 4 2 5 ... |
correct output |
---|
2 9 11 8 10 |
user output |
---|
2 8 9 10 11 |
Test 16
Verdict: WRONG ANSWER
input |
---|
7 1 2 1 3 2 4 2 5 ... |
correct output |
---|
2 5 7 4 6 |
user output |
---|
2 4 5 6 7 |
Test 17
Verdict: WRONG ANSWER
input |
---|
7 1 2 1 3 2 4 2 5 ... |
correct output |
---|
2 5 7 4 6 |
user output |
---|
2 4 5 6 7 |
Test 18
Verdict: WRONG ANSWER
input |
---|
10 8 4 3 4 4 6 2 3 ... |
correct output |
---|
3 8 7 10 9 1 6 |
user output |
---|
3 6 7 8 9 10 1 |
Test 19
Verdict: ACCEPTED
input |
---|
7 1 2 1 5 2 3 2 6 ... |
correct output |
---|
2 6 7 3 4 |
user output |
---|
2 3 4 6 7 |
Test 20
Verdict: WRONG ANSWER
input |
---|
8 1 2 1 3 2 4 2 5 ... |
correct output |
---|
3 4 7 6 8 1 5 |
user output |
---|
3 4 5 6 7 8 1 |
Test 21
Verdict: ACCEPTED
input |
---|
10 2 1 3 1 4 2 5 4 ... |
correct output |
---|
3 9 8 6 10 3 7 |
user output |
---|
3 3 6 7 8 9 10 |