Task: | Fragile network |
Sender: | aalto2024g_003 |
Submission time: | 2024-10-09 17:50:30 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | WRONG ANSWER | 0.01 s | details |
#3 | RUNTIME ERROR | 0.01 s | details |
#4 | WRONG ANSWER | 0.01 s | details |
#5 | WRONG ANSWER | 0.01 s | details |
#6 | ACCEPTED | 0.18 s | details |
#7 | WRONG ANSWER | 0.09 s | details |
#8 | WRONG ANSWER | 0.13 s | details |
#9 | WRONG ANSWER | 0.09 s | details |
#10 | WRONG ANSWER | 0.09 s | details |
#11 | WRONG ANSWER | 0.01 s | details |
#12 | WRONG ANSWER | 0.01 s | details |
#13 | WRONG ANSWER | 0.01 s | details |
#14 | WRONG ANSWER | 0.05 s | details |
#15 | RUNTIME ERROR | 0.01 s | details |
#16 | WRONG ANSWER | 0.01 s | details |
#17 | WRONG ANSWER | 0.01 s | details |
#18 | WRONG ANSWER | 0.01 s | details |
#19 | WRONG ANSWER | 0.01 s | details |
#20 | WRONG ANSWER | 0.01 s | details |
#21 | WRONG ANSWER | 0.01 s | details |
Compiler report
input/code.cpp: In function 'void dfs(long long int, long long int)': input/code.cpp:58:20: warning: statement has no effect [-Wunused-value] 58 | #define debug(...) 42 | ^~ input/code.cpp:68:5: note: in expansion of macro 'debug' 68 | debug(u, p); | ^~~~~ input/code.cpp:58:20: warning: statement has no effect [-Wunused-value] 58 | #define debug(...) 42 | ^~ input/code.cpp:77:9: note: in expansion of macro 'debug' 77 | debug(adj[u]); | ^~~~~
Code
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif const int N = 1e5 + 5; set<int> adj[N]; int n, nn; set<int> alive; bool vis[N]; void dfs(int u, int p) { debug(u, p); if (sz(adj[u]) == 2 && p) { if (adj[p].count(u)) adj[p].erase(u); int v = *adj[u].begin(); if (adj[v].count(u)) adj[v].erase(u); nn--; alive.erase(u); dfs(v, p); } else { debug(adj[u]); if (adj[u].empty()) return; vector<int> ele(all(adj[u])); for (int v : ele) { if (vis[v]) continue; vis[v] = 1; dfs(v, u); } } } signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); // RTE if input wrong datatype cin >> n; nn = n; for (int i = 1; i <= n; i++) alive.insert(i); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].insert(v); adj[v].insert(u); } vis[1] = 1; dfs(1, 0); if (sz(adj[1]) == 2) { int u = *adj[1].begin(); int v = *next(adj[1].begin()); if (adj[u].count(1)) adj[u].erase(1); if (adj[v].count(1)) adj[v].erase(1); adj[u].insert(v); adj[v].insert(u); nn--; alive.erase(1); } if (nn == 2) { cout << 1 << '\n'; int u = *alive.begin(); int v = *next(alive.begin()); cout << u << ' ' << v << '\n'; } else { int root = -1; for (int u : alive) { if (sz(adj[u]) > 1) { root = u; break; } } vector<pii> ans; vector<int> c(adj[root].begin(), adj[root].end()); for (int i = 0; i + 1 < sz(c); i += 2) { ans.push_back({c[i], c[i + 1]}); } if (sz(c) & 1) { ans.push_back({c[sz(c) - 2], c[sz(c) - 1]}); } cout << sz(ans) << '\n'; for (auto [u, v] : ans) cout << u << ' ' << v << '\n'; } }
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: WRONG ANSWER
input |
---|
10 4 5 3 4 2 3 9 10 ... |
correct output |
---|
1 10 1 |
user output |
---|
1 2 4 |
Test 3
Verdict: RUNTIME ERROR
input |
---|
10 1 8 1 3 3 5 5 7 ... |
correct output |
---|
3 7 10 8 2 1 9 |
user output |
---|
(empty) |
Test 4
Verdict: WRONG ANSWER
input |
---|
10 1 5 3 7 2 10 3 8 ... |
correct output |
---|
3 10 8 6 4 5 9 |
user output |
---|
2 2 5 5 6 |
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 |
---|
2 2 4 4 9 |
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: WRONG ANSWER
input |
---|
100000 92297 92298 23511 23512 68057 68058 65434 65435 ... |
correct output |
---|
1 100000 1 |
user output |
---|
1 2 4 |
Test 8
Verdict: WRONG ANSWER
input |
---|
100000 17747 97512 10397 12053 679 6975 4013 14565 ... |
correct output |
---|
25057 92881 76094 20353 87429 16069 96487 71186 52809 ... |
user output |
---|
6 2 3 19 29 43 108 265 638 ... |
Test 9
Verdict: WRONG ANSWER
input |
---|
100000 72941 72942 11232 11233 73464 73465 30042 30043 ... |
correct output |
---|
489 16423 85168 20707 94190 36505 54940 96411 44067 ... |
user output |
---|
1 2 4 |
Test 10
Verdict: WRONG ANSWER
input |
---|
100000 31451 31452 7473 7474 24056 24057 85181 85182 ... |
correct output |
---|
51 25638 2983 87594 87371 92001 50610 46744 100000 ... |
user output |
---|
1 2 4 |
Test 11
Verdict: WRONG ANSWER
input |
---|
10 1 2 1 3 3 4 3 5 ... |
correct output |
---|
2 2 6 4 10 |
user output |
---|
1 7 9 |
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 4 5 |
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 3 4 |
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 |
---|
2 2 3 3 4 |
Test 15
Verdict: RUNTIME ERROR
input |
---|
11 1 2 1 3 2 4 2 5 ... |
correct output |
---|
2 9 11 8 10 |
user output |
---|
(empty) |
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 3 4 4 5 |
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 3 4 4 5 |
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 |
---|
2 2 4 4 9 |
Test 19
Verdict: WRONG ANSWER
input |
---|
7 1 2 1 5 2 3 2 6 ... |
correct output |
---|
2 6 7 3 4 |
user output |
---|
2 3 5 5 6 |
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 1 4 5 6 6 7 |
Test 21
Verdict: WRONG ANSWER
input |
---|
10 2 1 3 1 4 2 5 4 ... |
correct output |
---|
3 9 8 6 10 3 7 |
user output |
---|
2 3 7 7 10 |