# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
394652 | 2021-04-27T06:48:27 Z | xxMen | Network (BOI15_net) | C++14 | 649 ms | 64848 KB |
#include "bits/stdc++.h" using namespace std; const int MAXN = 500007; bool odw[MAXN]; int leaves[MAXN]; int numleaves; vector <int> G[MAXN], S[MAXN]; void dfs(int v) { odw[v] = true; if((int)G[v].size() == 1) leaves[v] = 1; for(auto w : G[v]) if(odw[w]==false) { dfs(w); leaves[v] += leaves[w]; } } int findcut(int v) { odw[v] = true; for(auto w : G[v]) if(odw[w] == false) if(leaves[w] > numleaves/2) return findcut(w); return v; } void newdfs(int v, int tree) { //cerr << v << " " << tree << "T\n"; odw[v] = true; if((int)G[v].size() == 1) S[tree].push_back(v); for(auto w : G[v]) if(odw[w] == false) newdfs(w,tree); } int subtree; int cut(int n) { dfs(1); for(int i=1; i<=n; i++) odw[i] = false; int w = findcut(1); for(int i=1; i<=n; i++) odw[i] = false; odw[w] = true; for(auto v : G[w]) newdfs(v,++subtree); return w; } vector <int> W; int next(int e, int nn) { e += 2; if(e==nn) e = 1; return e; } int main() { int n; scanf("%d", &n); if(n==1) { printf("0\n"); return 0; } if(n==2) { printf("1\n1 2\n"); return 0; } for(int i=1; i<n; i++) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } for(int i=1; i<=n; i++) if((int)G[i].size() == 1) numleaves++; int res = (numleaves+1)/2; printf("%d\n", res); cut(n); W.resize(2*res); int e = 0; for(int i=1; i<=subtree; i++) { for(auto ele : S[i]) { W[e] = ele; e = next(e,2*res); //cerr << ele << "." << e << "\n"; } } if((!W.empty()) and W.back() == 0) W.back() = S[1][0]; for(int i=0; i<(int)W.size(); i+=2) printf("%d %d\n", W[i], W[i+1]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23756 KB | Output is correct |
2 | Correct | 14 ms | 23796 KB | Output is correct |
3 | Correct | 15 ms | 23756 KB | Output is correct |
4 | Correct | 15 ms | 23772 KB | Output is correct |
5 | Correct | 15 ms | 23756 KB | Output is correct |
6 | Correct | 14 ms | 23756 KB | Output is correct |
7 | Correct | 14 ms | 23784 KB | Output is correct |
8 | Correct | 16 ms | 23756 KB | Output is correct |
9 | Correct | 15 ms | 23792 KB | Output is correct |
10 | Correct | 17 ms | 23756 KB | Output is correct |
11 | Correct | 14 ms | 23756 KB | Output is correct |
12 | Correct | 14 ms | 23760 KB | Output is correct |
13 | Correct | 14 ms | 23764 KB | Output is correct |
14 | Correct | 13 ms | 23796 KB | Output is correct |
15 | Correct | 14 ms | 23756 KB | Output is correct |
16 | Correct | 14 ms | 23756 KB | Output is correct |
17 | Correct | 15 ms | 23792 KB | Output is correct |
18 | Correct | 14 ms | 23756 KB | Output is correct |
19 | Correct | 14 ms | 23756 KB | Output is correct |
20 | Correct | 14 ms | 23676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23756 KB | Output is correct |
2 | Correct | 14 ms | 23796 KB | Output is correct |
3 | Correct | 15 ms | 23756 KB | Output is correct |
4 | Correct | 15 ms | 23772 KB | Output is correct |
5 | Correct | 15 ms | 23756 KB | Output is correct |
6 | Correct | 14 ms | 23756 KB | Output is correct |
7 | Correct | 14 ms | 23784 KB | Output is correct |
8 | Correct | 16 ms | 23756 KB | Output is correct |
9 | Correct | 15 ms | 23792 KB | Output is correct |
10 | Correct | 17 ms | 23756 KB | Output is correct |
11 | Correct | 14 ms | 23756 KB | Output is correct |
12 | Correct | 14 ms | 23760 KB | Output is correct |
13 | Correct | 14 ms | 23764 KB | Output is correct |
14 | Correct | 13 ms | 23796 KB | Output is correct |
15 | Correct | 14 ms | 23756 KB | Output is correct |
16 | Correct | 14 ms | 23756 KB | Output is correct |
17 | Correct | 15 ms | 23792 KB | Output is correct |
18 | Correct | 14 ms | 23756 KB | Output is correct |
19 | Correct | 14 ms | 23756 KB | Output is correct |
20 | Correct | 14 ms | 23676 KB | Output is correct |
21 | Correct | 15 ms | 23796 KB | Output is correct |
22 | Correct | 16 ms | 23920 KB | Output is correct |
23 | Correct | 16 ms | 23888 KB | Output is correct |
24 | Correct | 16 ms | 23940 KB | Output is correct |
25 | Correct | 16 ms | 23888 KB | Output is correct |
26 | Correct | 16 ms | 23756 KB | Output is correct |
27 | Correct | 17 ms | 23768 KB | Output is correct |
28 | Correct | 16 ms | 23852 KB | Output is correct |
29 | Correct | 16 ms | 23744 KB | Output is correct |
30 | Correct | 16 ms | 23884 KB | Output is correct |
31 | Correct | 16 ms | 23772 KB | Output is correct |
32 | Correct | 15 ms | 23792 KB | Output is correct |
33 | Correct | 15 ms | 23756 KB | Output is correct |
34 | Correct | 15 ms | 23756 KB | Output is correct |
35 | Correct | 15 ms | 23748 KB | Output is correct |
36 | Correct | 14 ms | 23728 KB | Output is correct |
37 | Correct | 15 ms | 23756 KB | Output is correct |
38 | Correct | 16 ms | 23760 KB | Output is correct |
39 | Correct | 15 ms | 23680 KB | Output is correct |
40 | Correct | 15 ms | 23756 KB | Output is correct |
41 | Correct | 14 ms | 23756 KB | Output is correct |
42 | Correct | 15 ms | 23836 KB | Output is correct |
43 | Correct | 14 ms | 23872 KB | Output is correct |
44 | Correct | 15 ms | 23788 KB | Output is correct |
45 | Correct | 15 ms | 23756 KB | Output is correct |
46 | Correct | 15 ms | 23756 KB | Output is correct |
47 | Correct | 14 ms | 23756 KB | Output is correct |
48 | Correct | 14 ms | 23720 KB | Output is correct |
49 | Correct | 15 ms | 23756 KB | Output is correct |
50 | Correct | 15 ms | 23792 KB | Output is correct |
51 | Correct | 15 ms | 23784 KB | Output is correct |
52 | Correct | 15 ms | 23884 KB | Output is correct |
53 | Correct | 15 ms | 23756 KB | Output is correct |
54 | Correct | 14 ms | 23756 KB | Output is correct |
55 | Correct | 14 ms | 23756 KB | Output is correct |
56 | Correct | 15 ms | 23756 KB | Output is correct |
57 | Correct | 15 ms | 23788 KB | Output is correct |
58 | Correct | 15 ms | 23884 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23756 KB | Output is correct |
2 | Correct | 14 ms | 23796 KB | Output is correct |
3 | Correct | 15 ms | 23756 KB | Output is correct |
4 | Correct | 15 ms | 23772 KB | Output is correct |
5 | Correct | 15 ms | 23756 KB | Output is correct |
6 | Correct | 14 ms | 23756 KB | Output is correct |
7 | Correct | 14 ms | 23784 KB | Output is correct |
8 | Correct | 16 ms | 23756 KB | Output is correct |
9 | Correct | 15 ms | 23792 KB | Output is correct |
10 | Correct | 17 ms | 23756 KB | Output is correct |
11 | Correct | 14 ms | 23756 KB | Output is correct |
12 | Correct | 14 ms | 23760 KB | Output is correct |
13 | Correct | 14 ms | 23764 KB | Output is correct |
14 | Correct | 13 ms | 23796 KB | Output is correct |
15 | Correct | 14 ms | 23756 KB | Output is correct |
16 | Correct | 14 ms | 23756 KB | Output is correct |
17 | Correct | 15 ms | 23792 KB | Output is correct |
18 | Correct | 14 ms | 23756 KB | Output is correct |
19 | Correct | 14 ms | 23756 KB | Output is correct |
20 | Correct | 14 ms | 23676 KB | Output is correct |
21 | Correct | 15 ms | 23796 KB | Output is correct |
22 | Correct | 16 ms | 23920 KB | Output is correct |
23 | Correct | 16 ms | 23888 KB | Output is correct |
24 | Correct | 16 ms | 23940 KB | Output is correct |
25 | Correct | 16 ms | 23888 KB | Output is correct |
26 | Correct | 16 ms | 23756 KB | Output is correct |
27 | Correct | 17 ms | 23768 KB | Output is correct |
28 | Correct | 16 ms | 23852 KB | Output is correct |
29 | Correct | 16 ms | 23744 KB | Output is correct |
30 | Correct | 16 ms | 23884 KB | Output is correct |
31 | Correct | 16 ms | 23772 KB | Output is correct |
32 | Correct | 15 ms | 23792 KB | Output is correct |
33 | Correct | 15 ms | 23756 KB | Output is correct |
34 | Correct | 15 ms | 23756 KB | Output is correct |
35 | Correct | 15 ms | 23748 KB | Output is correct |
36 | Correct | 14 ms | 23728 KB | Output is correct |
37 | Correct | 15 ms | 23756 KB | Output is correct |
38 | Correct | 16 ms | 23760 KB | Output is correct |
39 | Correct | 15 ms | 23680 KB | Output is correct |
40 | Correct | 15 ms | 23756 KB | Output is correct |
41 | Correct | 14 ms | 23756 KB | Output is correct |
42 | Correct | 15 ms | 23836 KB | Output is correct |
43 | Correct | 14 ms | 23872 KB | Output is correct |
44 | Correct | 15 ms | 23788 KB | Output is correct |
45 | Correct | 15 ms | 23756 KB | Output is correct |
46 | Correct | 15 ms | 23756 KB | Output is correct |
47 | Correct | 14 ms | 23756 KB | Output is correct |
48 | Correct | 14 ms | 23720 KB | Output is correct |
49 | Correct | 15 ms | 23756 KB | Output is correct |
50 | Correct | 15 ms | 23792 KB | Output is correct |
51 | Correct | 15 ms | 23784 KB | Output is correct |
52 | Correct | 15 ms | 23884 KB | Output is correct |
53 | Correct | 15 ms | 23756 KB | Output is correct |
54 | Correct | 14 ms | 23756 KB | Output is correct |
55 | Correct | 14 ms | 23756 KB | Output is correct |
56 | Correct | 15 ms | 23756 KB | Output is correct |
57 | Correct | 15 ms | 23788 KB | Output is correct |
58 | Correct | 15 ms | 23884 KB | Output is correct |
59 | Correct | 462 ms | 48544 KB | Output is correct |
60 | Correct | 537 ms | 47952 KB | Output is correct |
61 | Correct | 15 ms | 23756 KB | Output is correct |
62 | Correct | 15 ms | 23784 KB | Output is correct |
63 | Correct | 412 ms | 45040 KB | Output is correct |
64 | Correct | 21 ms | 24164 KB | Output is correct |
65 | Correct | 32 ms | 25788 KB | Output is correct |
66 | Correct | 194 ms | 41088 KB | Output is correct |
67 | Correct | 621 ms | 58760 KB | Output is correct |
68 | Correct | 649 ms | 59708 KB | Output is correct |
69 | Correct | 23 ms | 24908 KB | Output is correct |
70 | Correct | 119 ms | 35880 KB | Output is correct |
71 | Correct | 481 ms | 64848 KB | Output is correct |
72 | Correct | 459 ms | 62400 KB | Output is correct |
73 | Correct | 110 ms | 30024 KB | Output is correct |
74 | Correct | 556 ms | 46336 KB | Output is correct |
75 | Correct | 43 ms | 27284 KB | Output is correct |
76 | Correct | 407 ms | 57228 KB | Output is correct |
77 | Correct | 395 ms | 57932 KB | Output is correct |
78 | Correct | 46 ms | 26980 KB | Output is correct |
79 | Correct | 647 ms | 56312 KB | Output is correct |
80 | Correct | 17 ms | 24012 KB | Output is correct |
81 | Correct | 135 ms | 34360 KB | Output is correct |
82 | Correct | 503 ms | 55608 KB | Output is correct |
83 | Correct | 557 ms | 46216 KB | Output is correct |
84 | Correct | 555 ms | 46376 KB | Output is correct |
85 | Correct | 563 ms | 46504 KB | Output is correct |
86 | Correct | 540 ms | 47584 KB | Output is correct |
87 | Correct | 531 ms | 47936 KB | Output is correct |