# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
31424 | 2017-08-22T16:07:55 Z | imaxblue | Network (BOI15_net) | C++14 | 853 ms | 66264 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() (rand() >> 3)*rand() int n, a, b, c, r[500005]; vector<int> v[500005], com[500005]; vector<pii> ans; int mrg(int A, int B){ if (com[A].size()<com[B].size()) return mrg(B, A); fox(l, com[B].size()){ //cout << "*" << A << ' ' << B << ' ' << com[A].size() << ' ' << com[B].size() << ' ' << n << endl; if (com[A].size()+com[B].size()-l>(c+1)/2){ c-=2; ans.pb(mp(com[A].back(), com[B][l])); com[A].pop_back(); } else com[A].pb(com[B][l]); } return A; } void dfs(int N, int P){ if (v[N].size()==1){ r[N]=N; com[N]=vector<int>(1, N); return; } int best=-1; fox(l, v[N].size()){ if (v[N][l]==P) continue; dfs(v[N][l], N); if (best==-1 || com[r[v[N][l]]].size()>com[best].size()) best=r[v[N][l]]; } fox(l, v[N].size()){ if (v[N][l]==P || r[v[N][l]]==best) continue; mrg(best, r[v[N][l]]); } r[N]=best; //cout << N << ' ' << r[N] << endl; } int main(){ scanf("%i", &n); fox(l, n-1){ scanf("%i%i", &a, &b); v[a].pb(b); v[b].pb(a); } fox1(l, n){ if (v[l].size()==1) c++; } fox1(l, n){ if (v[l].size()>1){ dfs(l, -1); //cout << com[r[l]].size() << endl; if (com[r[l]].size()){ ans.pb(mp(com[r[l]][0], ans.back().y)); } printf("%i\n", ans.size()); fox(l2, ans.size()){ printf("%i %i\n", ans[l2].x, ans[l2].y); } return 0; } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 27408 KB | Output is correct |
2 | Correct | 6 ms | 27408 KB | Output is correct |
3 | Correct | 9 ms | 27408 KB | Output is correct |
4 | Correct | 6 ms | 27408 KB | Output is correct |
5 | Correct | 6 ms | 27408 KB | Output is correct |
6 | Correct | 6 ms | 27408 KB | Output is correct |
7 | Correct | 9 ms | 27408 KB | Output is correct |
8 | Correct | 6 ms | 27408 KB | Output is correct |
9 | Correct | 3 ms | 27408 KB | Output is correct |
10 | Correct | 6 ms | 27408 KB | Output is correct |
11 | Correct | 6 ms | 27408 KB | Output is correct |
12 | Correct | 6 ms | 27408 KB | Output is correct |
13 | Correct | 6 ms | 27408 KB | Output is correct |
14 | Correct | 6 ms | 27408 KB | Output is correct |
15 | Correct | 13 ms | 27408 KB | Output is correct |
16 | Correct | 9 ms | 27408 KB | Output is correct |
17 | Correct | 6 ms | 27408 KB | Output is correct |
18 | Correct | 6 ms | 27408 KB | Output is correct |
19 | Correct | 3 ms | 27408 KB | Output is correct |
20 | Correct | 9 ms | 27408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 27408 KB | Output is correct |
2 | Correct | 6 ms | 27408 KB | Output is correct |
3 | Correct | 9 ms | 27408 KB | Output is correct |
4 | Correct | 6 ms | 27408 KB | Output is correct |
5 | Correct | 6 ms | 27408 KB | Output is correct |
6 | Correct | 6 ms | 27408 KB | Output is correct |
7 | Correct | 9 ms | 27408 KB | Output is correct |
8 | Correct | 6 ms | 27408 KB | Output is correct |
9 | Correct | 3 ms | 27408 KB | Output is correct |
10 | Correct | 6 ms | 27408 KB | Output is correct |
11 | Correct | 6 ms | 27408 KB | Output is correct |
12 | Correct | 6 ms | 27408 KB | Output is correct |
13 | Correct | 6 ms | 27408 KB | Output is correct |
14 | Correct | 6 ms | 27408 KB | Output is correct |
15 | Correct | 13 ms | 27408 KB | Output is correct |
16 | Correct | 9 ms | 27408 KB | Output is correct |
17 | Correct | 6 ms | 27408 KB | Output is correct |
18 | Correct | 6 ms | 27408 KB | Output is correct |
19 | Correct | 3 ms | 27408 KB | Output is correct |
20 | Correct | 9 ms | 27408 KB | Output is correct |
21 | Correct | 6 ms | 27408 KB | Output is correct |
22 | Correct | 9 ms | 27540 KB | Output is correct |
23 | Correct | 6 ms | 27540 KB | Output is correct |
24 | Correct | 9 ms | 27540 KB | Output is correct |
25 | Correct | 3 ms | 27540 KB | Output is correct |
26 | Correct | 3 ms | 27540 KB | Output is correct |
27 | Correct | 9 ms | 27540 KB | Output is correct |
28 | Correct | 9 ms | 27540 KB | Output is correct |
29 | Correct | 9 ms | 27540 KB | Output is correct |
30 | Correct | 6 ms | 27408 KB | Output is correct |
31 | Correct | 3 ms | 27540 KB | Output is correct |
32 | Correct | 9 ms | 27408 KB | Output is correct |
33 | Correct | 6 ms | 27408 KB | Output is correct |
34 | Correct | 6 ms | 27408 KB | Output is correct |
35 | Correct | 6 ms | 27408 KB | Output is correct |
36 | Correct | 6 ms | 27408 KB | Output is correct |
37 | Correct | 6 ms | 27408 KB | Output is correct |
38 | Correct | 13 ms | 27408 KB | Output is correct |
39 | Correct | 3 ms | 27408 KB | Output is correct |
40 | Correct | 6 ms | 27408 KB | Output is correct |
41 | Correct | 6 ms | 27408 KB | Output is correct |
42 | Correct | 9 ms | 27408 KB | Output is correct |
43 | Correct | 0 ms | 27540 KB | Output is correct |
44 | Correct | 3 ms | 27408 KB | Output is correct |
45 | Correct | 3 ms | 27408 KB | Output is correct |
46 | Correct | 6 ms | 27540 KB | Output is correct |
47 | Correct | 6 ms | 27408 KB | Output is correct |
48 | Correct | 3 ms | 27408 KB | Output is correct |
49 | Correct | 6 ms | 27540 KB | Output is correct |
50 | Correct | 9 ms | 27408 KB | Output is correct |
51 | Correct | 6 ms | 27408 KB | Output is correct |
52 | Correct | 9 ms | 27408 KB | Output is correct |
53 | Correct | 0 ms | 27408 KB | Output is correct |
54 | Correct | 3 ms | 27408 KB | Output is correct |
55 | Correct | 0 ms | 27408 KB | Output is correct |
56 | Correct | 3 ms | 27408 KB | Output is correct |
57 | Correct | 3 ms | 27408 KB | Output is correct |
58 | Correct | 3 ms | 27540 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 27408 KB | Output is correct |
2 | Correct | 6 ms | 27408 KB | Output is correct |
3 | Correct | 9 ms | 27408 KB | Output is correct |
4 | Correct | 6 ms | 27408 KB | Output is correct |
5 | Correct | 6 ms | 27408 KB | Output is correct |
6 | Correct | 6 ms | 27408 KB | Output is correct |
7 | Correct | 9 ms | 27408 KB | Output is correct |
8 | Correct | 6 ms | 27408 KB | Output is correct |
9 | Correct | 3 ms | 27408 KB | Output is correct |
10 | Correct | 6 ms | 27408 KB | Output is correct |
11 | Correct | 6 ms | 27408 KB | Output is correct |
12 | Correct | 6 ms | 27408 KB | Output is correct |
13 | Correct | 6 ms | 27408 KB | Output is correct |
14 | Correct | 6 ms | 27408 KB | Output is correct |
15 | Correct | 13 ms | 27408 KB | Output is correct |
16 | Correct | 9 ms | 27408 KB | Output is correct |
17 | Correct | 6 ms | 27408 KB | Output is correct |
18 | Correct | 6 ms | 27408 KB | Output is correct |
19 | Correct | 3 ms | 27408 KB | Output is correct |
20 | Correct | 9 ms | 27408 KB | Output is correct |
21 | Correct | 6 ms | 27408 KB | Output is correct |
22 | Correct | 9 ms | 27540 KB | Output is correct |
23 | Correct | 6 ms | 27540 KB | Output is correct |
24 | Correct | 9 ms | 27540 KB | Output is correct |
25 | Correct | 3 ms | 27540 KB | Output is correct |
26 | Correct | 3 ms | 27540 KB | Output is correct |
27 | Correct | 9 ms | 27540 KB | Output is correct |
28 | Correct | 9 ms | 27540 KB | Output is correct |
29 | Correct | 9 ms | 27540 KB | Output is correct |
30 | Correct | 6 ms | 27408 KB | Output is correct |
31 | Correct | 3 ms | 27540 KB | Output is correct |
32 | Correct | 9 ms | 27408 KB | Output is correct |
33 | Correct | 6 ms | 27408 KB | Output is correct |
34 | Correct | 6 ms | 27408 KB | Output is correct |
35 | Correct | 6 ms | 27408 KB | Output is correct |
36 | Correct | 6 ms | 27408 KB | Output is correct |
37 | Correct | 6 ms | 27408 KB | Output is correct |
38 | Correct | 13 ms | 27408 KB | Output is correct |
39 | Correct | 3 ms | 27408 KB | Output is correct |
40 | Correct | 6 ms | 27408 KB | Output is correct |
41 | Correct | 6 ms | 27408 KB | Output is correct |
42 | Correct | 9 ms | 27408 KB | Output is correct |
43 | Correct | 0 ms | 27540 KB | Output is correct |
44 | Correct | 3 ms | 27408 KB | Output is correct |
45 | Correct | 3 ms | 27408 KB | Output is correct |
46 | Correct | 6 ms | 27540 KB | Output is correct |
47 | Correct | 6 ms | 27408 KB | Output is correct |
48 | Correct | 3 ms | 27408 KB | Output is correct |
49 | Correct | 6 ms | 27540 KB | Output is correct |
50 | Correct | 9 ms | 27408 KB | Output is correct |
51 | Correct | 6 ms | 27408 KB | Output is correct |
52 | Correct | 9 ms | 27408 KB | Output is correct |
53 | Correct | 0 ms | 27408 KB | Output is correct |
54 | Correct | 3 ms | 27408 KB | Output is correct |
55 | Correct | 0 ms | 27408 KB | Output is correct |
56 | Correct | 3 ms | 27408 KB | Output is correct |
57 | Correct | 3 ms | 27408 KB | Output is correct |
58 | Correct | 3 ms | 27540 KB | Output is correct |
59 | Correct | 673 ms | 56056 KB | Output is correct |
60 | Correct | 603 ms | 65032 KB | Output is correct |
61 | Correct | 6 ms | 27408 KB | Output is correct |
62 | Correct | 3 ms | 27408 KB | Output is correct |
63 | Correct | 396 ms | 53984 KB | Output is correct |
64 | Correct | 0 ms | 27800 KB | Output is correct |
65 | Correct | 13 ms | 29488 KB | Output is correct |
66 | Correct | 109 ms | 46236 KB | Output is correct |
67 | Correct | 536 ms | 63800 KB | Output is correct |
68 | Correct | 583 ms | 66264 KB | Output is correct |
69 | Correct | 19 ms | 28508 KB | Output is correct |
70 | Correct | 109 ms | 40252 KB | Output is correct |
71 | Correct | 503 ms | 65912 KB | Output is correct |
72 | Correct | 609 ms | 63856 KB | Output is correct |
73 | Correct | 196 ms | 36280 KB | Output is correct |
74 | Correct | 829 ms | 58012 KB | Output is correct |
75 | Correct | 43 ms | 31608 KB | Output is correct |
76 | Correct | 563 ms | 64248 KB | Output is correct |
77 | Correct | 599 ms | 64900 KB | Output is correct |
78 | Correct | 53 ms | 31120 KB | Output is correct |
79 | Correct | 746 ms | 60896 KB | Output is correct |
80 | Correct | 9 ms | 27672 KB | Output is correct |
81 | Correct | 146 ms | 38976 KB | Output is correct |
82 | Correct | 779 ms | 63596 KB | Output is correct |
83 | Correct | 839 ms | 58080 KB | Output is correct |
84 | Correct | 853 ms | 57800 KB | Output is correct |
85 | Correct | 833 ms | 58056 KB | Output is correct |
86 | Correct | 749 ms | 64480 KB | Output is correct |
87 | Correct | 656 ms | 63696 KB | Output is correct |