# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
394612 |
2021-04-27T05:52:25 Z |
fammo |
Network (BOI15_net) |
C++11 |
|
938 ms |
85704 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define endl '\n'
//#define int ll
const int N = 500 * 1000 + 20, MOD = 1e9+7, base =727;
int n, st[N], low[N], tim;
vector<int>adj[N], leaf;
vector<pii>g[N];
bool mark[N];
void dfs(int v, int p){
if(int(adj[v].size()) == 1)leaf.pb(v);
for(int u : adj[v])if(u!=p)dfs(u,v);
return;
}void check(int v, int e){
st[v] = low[v] = ++tim;
mark[v] = 1;
for(auto p : g[v]){
int u = p.first, i = p.second;
if(!mark[u]){
check(u, i);
low[v] = min(low[u], low[v]);
if(low[u] > st[v])
while(1)tim++;
}
else if(i != e)
low[v] = min(low[v], st[u]);
}
return;
}
int32_t main(){
fastio;
///auto t = clock();
cin >> n;
for(int i = 0; i < n - 1; i ++){
int u, v;
cin >> u >> v;
u --; v --;
adj[u].pb(v); adj[v].pb(u);
g[v].pb({u,i}); g[u].pb({v,i});
}int root = 0;
for(int i = 0; i < n; i ++){if(int(adj[i].size()) >2){root = i;}}
if(int(adj[root].size()<=2)){
cout << 1 << endl;
for(int i =0 ; i < n; i ++)if((int)adj[i].size() == 1)cout << i +1 << ' ';
cout << endl;
return 0;
}
dfs(root,-1);
int k = (int(leaf.size()))/2;
int ans = (int(leaf.size()) + 1)/2;
for(int i = 0; i < ans; i ++){
int u = leaf[i], v = leaf[i+k];
g[v].pb({u,i+n-1}); g[u].pb({v,i+n-1});
}
check(root,-1);
cout << ans << endl;
for(int i = 0; i < ans; i ++){
cout << leaf[i] + 1 << ' ' << leaf[i+k] + 1 << endl;
}
///cout << clock() - t << "ms" << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
15 ms |
23808 KB |
Output is correct |
3 |
Correct |
15 ms |
23724 KB |
Output is correct |
4 |
Correct |
15 ms |
23768 KB |
Output is correct |
5 |
Correct |
15 ms |
23788 KB |
Output is correct |
6 |
Correct |
15 ms |
23756 KB |
Output is correct |
7 |
Correct |
15 ms |
23820 KB |
Output is correct |
8 |
Correct |
15 ms |
23756 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
15 ms |
23820 KB |
Output is correct |
11 |
Correct |
15 ms |
23740 KB |
Output is correct |
12 |
Correct |
14 ms |
23712 KB |
Output is correct |
13 |
Correct |
16 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23700 KB |
Output is correct |
15 |
Correct |
15 ms |
23756 KB |
Output is correct |
16 |
Correct |
16 ms |
23828 KB |
Output is correct |
17 |
Correct |
16 ms |
23884 KB |
Output is correct |
18 |
Correct |
15 ms |
23760 KB |
Output is correct |
19 |
Correct |
15 ms |
23756 KB |
Output is correct |
20 |
Correct |
15 ms |
23728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
15 ms |
23808 KB |
Output is correct |
3 |
Correct |
15 ms |
23724 KB |
Output is correct |
4 |
Correct |
15 ms |
23768 KB |
Output is correct |
5 |
Correct |
15 ms |
23788 KB |
Output is correct |
6 |
Correct |
15 ms |
23756 KB |
Output is correct |
7 |
Correct |
15 ms |
23820 KB |
Output is correct |
8 |
Correct |
15 ms |
23756 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
15 ms |
23820 KB |
Output is correct |
11 |
Correct |
15 ms |
23740 KB |
Output is correct |
12 |
Correct |
14 ms |
23712 KB |
Output is correct |
13 |
Correct |
16 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23700 KB |
Output is correct |
15 |
Correct |
15 ms |
23756 KB |
Output is correct |
16 |
Correct |
16 ms |
23828 KB |
Output is correct |
17 |
Correct |
16 ms |
23884 KB |
Output is correct |
18 |
Correct |
15 ms |
23760 KB |
Output is correct |
19 |
Correct |
15 ms |
23756 KB |
Output is correct |
20 |
Correct |
15 ms |
23728 KB |
Output is correct |
21 |
Correct |
14 ms |
23808 KB |
Output is correct |
22 |
Correct |
16 ms |
23964 KB |
Output is correct |
23 |
Correct |
16 ms |
24012 KB |
Output is correct |
24 |
Correct |
16 ms |
23884 KB |
Output is correct |
25 |
Correct |
16 ms |
23884 KB |
Output is correct |
26 |
Correct |
16 ms |
23844 KB |
Output is correct |
27 |
Correct |
16 ms |
24040 KB |
Output is correct |
28 |
Correct |
17 ms |
24028 KB |
Output is correct |
29 |
Correct |
16 ms |
23884 KB |
Output is correct |
30 |
Correct |
15 ms |
23756 KB |
Output is correct |
31 |
Correct |
17 ms |
24040 KB |
Output is correct |
32 |
Correct |
15 ms |
23760 KB |
Output is correct |
33 |
Correct |
16 ms |
23756 KB |
Output is correct |
34 |
Correct |
15 ms |
23800 KB |
Output is correct |
35 |
Correct |
15 ms |
23772 KB |
Output is correct |
36 |
Correct |
16 ms |
23756 KB |
Output is correct |
37 |
Correct |
16 ms |
23848 KB |
Output is correct |
38 |
Correct |
18 ms |
23884 KB |
Output is correct |
39 |
Correct |
16 ms |
23720 KB |
Output is correct |
40 |
Correct |
15 ms |
23828 KB |
Output is correct |
41 |
Correct |
16 ms |
23732 KB |
Output is correct |
42 |
Correct |
16 ms |
23868 KB |
Output is correct |
43 |
Correct |
16 ms |
23884 KB |
Output is correct |
44 |
Correct |
15 ms |
23820 KB |
Output is correct |
45 |
Correct |
15 ms |
23756 KB |
Output is correct |
46 |
Correct |
15 ms |
23824 KB |
Output is correct |
47 |
Correct |
15 ms |
23704 KB |
Output is correct |
48 |
Correct |
16 ms |
23756 KB |
Output is correct |
49 |
Correct |
16 ms |
23884 KB |
Output is correct |
50 |
Correct |
15 ms |
23756 KB |
Output is correct |
51 |
Correct |
15 ms |
23756 KB |
Output is correct |
52 |
Correct |
16 ms |
23756 KB |
Output is correct |
53 |
Correct |
16 ms |
23884 KB |
Output is correct |
54 |
Correct |
15 ms |
23756 KB |
Output is correct |
55 |
Correct |
16 ms |
23756 KB |
Output is correct |
56 |
Correct |
16 ms |
23756 KB |
Output is correct |
57 |
Correct |
15 ms |
23872 KB |
Output is correct |
58 |
Correct |
16 ms |
24000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
15 ms |
23808 KB |
Output is correct |
3 |
Correct |
15 ms |
23724 KB |
Output is correct |
4 |
Correct |
15 ms |
23768 KB |
Output is correct |
5 |
Correct |
15 ms |
23788 KB |
Output is correct |
6 |
Correct |
15 ms |
23756 KB |
Output is correct |
7 |
Correct |
15 ms |
23820 KB |
Output is correct |
8 |
Correct |
15 ms |
23756 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
15 ms |
23820 KB |
Output is correct |
11 |
Correct |
15 ms |
23740 KB |
Output is correct |
12 |
Correct |
14 ms |
23712 KB |
Output is correct |
13 |
Correct |
16 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23700 KB |
Output is correct |
15 |
Correct |
15 ms |
23756 KB |
Output is correct |
16 |
Correct |
16 ms |
23828 KB |
Output is correct |
17 |
Correct |
16 ms |
23884 KB |
Output is correct |
18 |
Correct |
15 ms |
23760 KB |
Output is correct |
19 |
Correct |
15 ms |
23756 KB |
Output is correct |
20 |
Correct |
15 ms |
23728 KB |
Output is correct |
21 |
Correct |
14 ms |
23808 KB |
Output is correct |
22 |
Correct |
16 ms |
23964 KB |
Output is correct |
23 |
Correct |
16 ms |
24012 KB |
Output is correct |
24 |
Correct |
16 ms |
23884 KB |
Output is correct |
25 |
Correct |
16 ms |
23884 KB |
Output is correct |
26 |
Correct |
16 ms |
23844 KB |
Output is correct |
27 |
Correct |
16 ms |
24040 KB |
Output is correct |
28 |
Correct |
17 ms |
24028 KB |
Output is correct |
29 |
Correct |
16 ms |
23884 KB |
Output is correct |
30 |
Correct |
15 ms |
23756 KB |
Output is correct |
31 |
Correct |
17 ms |
24040 KB |
Output is correct |
32 |
Correct |
15 ms |
23760 KB |
Output is correct |
33 |
Correct |
16 ms |
23756 KB |
Output is correct |
34 |
Correct |
15 ms |
23800 KB |
Output is correct |
35 |
Correct |
15 ms |
23772 KB |
Output is correct |
36 |
Correct |
16 ms |
23756 KB |
Output is correct |
37 |
Correct |
16 ms |
23848 KB |
Output is correct |
38 |
Correct |
18 ms |
23884 KB |
Output is correct |
39 |
Correct |
16 ms |
23720 KB |
Output is correct |
40 |
Correct |
15 ms |
23828 KB |
Output is correct |
41 |
Correct |
16 ms |
23732 KB |
Output is correct |
42 |
Correct |
16 ms |
23868 KB |
Output is correct |
43 |
Correct |
16 ms |
23884 KB |
Output is correct |
44 |
Correct |
15 ms |
23820 KB |
Output is correct |
45 |
Correct |
15 ms |
23756 KB |
Output is correct |
46 |
Correct |
15 ms |
23824 KB |
Output is correct |
47 |
Correct |
15 ms |
23704 KB |
Output is correct |
48 |
Correct |
16 ms |
23756 KB |
Output is correct |
49 |
Correct |
16 ms |
23884 KB |
Output is correct |
50 |
Correct |
15 ms |
23756 KB |
Output is correct |
51 |
Correct |
15 ms |
23756 KB |
Output is correct |
52 |
Correct |
16 ms |
23756 KB |
Output is correct |
53 |
Correct |
16 ms |
23884 KB |
Output is correct |
54 |
Correct |
15 ms |
23756 KB |
Output is correct |
55 |
Correct |
16 ms |
23756 KB |
Output is correct |
56 |
Correct |
16 ms |
23756 KB |
Output is correct |
57 |
Correct |
15 ms |
23872 KB |
Output is correct |
58 |
Correct |
16 ms |
24000 KB |
Output is correct |
59 |
Correct |
768 ms |
63324 KB |
Output is correct |
60 |
Correct |
937 ms |
70812 KB |
Output is correct |
61 |
Correct |
16 ms |
23756 KB |
Output is correct |
62 |
Correct |
15 ms |
23700 KB |
Output is correct |
63 |
Correct |
665 ms |
58448 KB |
Output is correct |
64 |
Correct |
19 ms |
24396 KB |
Output is correct |
65 |
Correct |
32 ms |
26724 KB |
Output is correct |
66 |
Correct |
273 ms |
43288 KB |
Output is correct |
67 |
Correct |
624 ms |
55236 KB |
Output is correct |
68 |
Correct |
910 ms |
81856 KB |
Output is correct |
69 |
Correct |
25 ms |
25164 KB |
Output is correct |
70 |
Correct |
186 ms |
39328 KB |
Output is correct |
71 |
Correct |
649 ms |
72732 KB |
Output is correct |
72 |
Correct |
684 ms |
71904 KB |
Output is correct |
73 |
Correct |
204 ms |
36284 KB |
Output is correct |
74 |
Correct |
912 ms |
67780 KB |
Output is correct |
75 |
Correct |
56 ms |
29060 KB |
Output is correct |
76 |
Correct |
721 ms |
70400 KB |
Output is correct |
77 |
Correct |
663 ms |
70828 KB |
Output is correct |
78 |
Correct |
64 ms |
29468 KB |
Output is correct |
79 |
Correct |
897 ms |
85704 KB |
Output is correct |
80 |
Correct |
18 ms |
24140 KB |
Output is correct |
81 |
Correct |
232 ms |
39344 KB |
Output is correct |
82 |
Correct |
778 ms |
68392 KB |
Output is correct |
83 |
Correct |
913 ms |
67776 KB |
Output is correct |
84 |
Correct |
906 ms |
68112 KB |
Output is correct |
85 |
Correct |
906 ms |
67768 KB |
Output is correct |
86 |
Correct |
920 ms |
69608 KB |
Output is correct |
87 |
Correct |
938 ms |
70140 KB |
Output is correct |