# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
197125 | 2020-01-19T05:27:46 Z | arnold518 | Railway (BOI17_railway) | C++14 | 406 ms | 33312 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; int N, M, K; vector<pii> adj[MAXN+10]; vector<int> A[MAXN+10]; int idx[MAXN+10], cnt, C[MAXN+10]; int par[MAXN+10][30], dep[MAXN+10]; void dfs(int now, int bef, int depth) { par[now][0]=bef; dep[now]=depth; idx[now]=++cnt; for(auto nxt : adj[now]) { if(nxt.first==bef) continue; dfs(nxt.first, now, depth+1); } } int lca(int u, int v) { int i, j; if(dep[u]>dep[v]) swap(u, v); for(i=20; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i]; if(u==v) return u; for(i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i]; return par[u][0]; } vector<int> ans; void dfs2(int now, int bef, int num) { for(auto nxt : adj[now]) { if(nxt.first==bef) continue; dfs2(nxt.first, now, nxt.second); C[now]+=C[nxt.first]; } if(num && C[now]>=2*K) ans.push_back(num); } int main() { int i, j; scanf("%d%d%d", &N, &M, &K); for(i=1; i<N; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back({v, i}); adj[v].push_back({u, i}); } dfs(1, 1, 1); for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1]; for(i=1; i<=M; i++) { int p; scanf("%d", &p); for(j=0; j<p; j++) { int t; scanf("%d", &t); A[i].push_back(t); } sort(A[i].begin(), A[i].end(), [&](const int &p, const int &q) { return idx[p]<idx[q]; }); A[i].push_back(A[i][0]); for(j=1; j<A[i].size(); j++) { int p=A[i][j-1], q=A[i][j]; int w=lca(p, q); C[w]--; C[w]--; C[p]++; C[q]++; } } dfs2(1, 1, 0); printf("%d\n", ans.size()); sort(ans.begin(), ans.end()); for(auto it : ans) printf("%d ", it); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 17 ms | 6776 KB | Output is correct |
3 | Correct | 16 ms | 6776 KB | Output is correct |
4 | Correct | 8 ms | 5112 KB | Output is correct |
5 | Correct | 8 ms | 5112 KB | Output is correct |
6 | Correct | 17 ms | 7292 KB | Output is correct |
7 | Correct | 16 ms | 6904 KB | Output is correct |
8 | Correct | 15 ms | 6904 KB | Output is correct |
9 | Correct | 16 ms | 6876 KB | Output is correct |
10 | Correct | 8 ms | 4984 KB | Output is correct |
11 | Correct | 8 ms | 4984 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 8 ms | 5084 KB | Output is correct |
14 | Correct | 8 ms | 5112 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 17 ms | 6776 KB | Output is correct |
3 | Correct | 16 ms | 6776 KB | Output is correct |
4 | Correct | 8 ms | 5112 KB | Output is correct |
5 | Correct | 8 ms | 5112 KB | Output is correct |
6 | Correct | 17 ms | 7292 KB | Output is correct |
7 | Correct | 16 ms | 6904 KB | Output is correct |
8 | Correct | 15 ms | 6904 KB | Output is correct |
9 | Correct | 16 ms | 6876 KB | Output is correct |
10 | Correct | 8 ms | 4984 KB | Output is correct |
11 | Correct | 8 ms | 4984 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 8 ms | 5084 KB | Output is correct |
14 | Correct | 8 ms | 5112 KB | Output is correct |
15 | Correct | 45 ms | 7672 KB | Output is correct |
16 | Correct | 50 ms | 7780 KB | Output is correct |
17 | Correct | 50 ms | 7756 KB | Output is correct |
18 | Correct | 18 ms | 7288 KB | Output is correct |
19 | Correct | 16 ms | 6900 KB | Output is correct |
20 | Correct | 54 ms | 7900 KB | Output is correct |
21 | Correct | 62 ms | 7800 KB | Output is correct |
22 | Correct | 8 ms | 5112 KB | Output is correct |
23 | Correct | 15 ms | 6776 KB | Output is correct |
24 | Correct | 17 ms | 6860 KB | Output is correct |
25 | Correct | 8 ms | 4984 KB | Output is correct |
26 | Correct | 6 ms | 5112 KB | Output is correct |
27 | Correct | 54 ms | 7288 KB | Output is correct |
28 | Correct | 16 ms | 6904 KB | Output is correct |
29 | Correct | 15 ms | 6780 KB | Output is correct |
30 | Correct | 15 ms | 6904 KB | Output is correct |
31 | Correct | 8 ms | 5100 KB | Output is correct |
32 | Correct | 8 ms | 4984 KB | Output is correct |
33 | Correct | 10 ms | 5112 KB | Output is correct |
34 | Correct | 8 ms | 5108 KB | Output is correct |
35 | Correct | 6 ms | 4984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 190 ms | 31412 KB | Output is correct |
2 | Correct | 8 ms | 4984 KB | Output is correct |
3 | Correct | 182 ms | 32888 KB | Output is correct |
4 | Correct | 175 ms | 32248 KB | Output is correct |
5 | Correct | 406 ms | 32536 KB | Output is correct |
6 | Correct | 181 ms | 32852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 168 ms | 27064 KB | Output is correct |
2 | Correct | 180 ms | 25536 KB | Output is correct |
3 | Correct | 200 ms | 25020 KB | Output is correct |
4 | Correct | 205 ms | 25080 KB | Output is correct |
5 | Correct | 207 ms | 24952 KB | Output is correct |
6 | Correct | 270 ms | 29180 KB | Output is correct |
7 | Correct | 152 ms | 28912 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 168 ms | 27064 KB | Output is correct |
2 | Correct | 180 ms | 25536 KB | Output is correct |
3 | Correct | 200 ms | 25020 KB | Output is correct |
4 | Correct | 205 ms | 25080 KB | Output is correct |
5 | Correct | 207 ms | 24952 KB | Output is correct |
6 | Correct | 270 ms | 29180 KB | Output is correct |
7 | Correct | 152 ms | 28912 KB | Output is correct |
8 | Correct | 195 ms | 28408 KB | Output is correct |
9 | Correct | 197 ms | 28380 KB | Output is correct |
10 | Correct | 187 ms | 32172 KB | Output is correct |
11 | Correct | 186 ms | 32108 KB | Output is correct |
12 | Correct | 132 ms | 23672 KB | Output is correct |
13 | Correct | 129 ms | 23772 KB | Output is correct |
14 | Correct | 153 ms | 24036 KB | Output is correct |
15 | Correct | 194 ms | 24420 KB | Output is correct |
16 | Correct | 165 ms | 25024 KB | Output is correct |
17 | Correct | 165 ms | 25100 KB | Output is correct |
18 | Correct | 162 ms | 25080 KB | Output is correct |
19 | Correct | 173 ms | 25436 KB | Output is correct |
20 | Correct | 165 ms | 29304 KB | Output is correct |
21 | Correct | 165 ms | 29396 KB | Output is correct |
22 | Correct | 158 ms | 29304 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 17 ms | 6776 KB | Output is correct |
3 | Correct | 16 ms | 6776 KB | Output is correct |
4 | Correct | 8 ms | 5112 KB | Output is correct |
5 | Correct | 8 ms | 5112 KB | Output is correct |
6 | Correct | 17 ms | 7292 KB | Output is correct |
7 | Correct | 16 ms | 6904 KB | Output is correct |
8 | Correct | 15 ms | 6904 KB | Output is correct |
9 | Correct | 16 ms | 6876 KB | Output is correct |
10 | Correct | 8 ms | 4984 KB | Output is correct |
11 | Correct | 8 ms | 4984 KB | Output is correct |
12 | Correct | 7 ms | 5112 KB | Output is correct |
13 | Correct | 8 ms | 5084 KB | Output is correct |
14 | Correct | 8 ms | 5112 KB | Output is correct |
15 | Correct | 45 ms | 7672 KB | Output is correct |
16 | Correct | 50 ms | 7780 KB | Output is correct |
17 | Correct | 50 ms | 7756 KB | Output is correct |
18 | Correct | 18 ms | 7288 KB | Output is correct |
19 | Correct | 16 ms | 6900 KB | Output is correct |
20 | Correct | 54 ms | 7900 KB | Output is correct |
21 | Correct | 62 ms | 7800 KB | Output is correct |
22 | Correct | 8 ms | 5112 KB | Output is correct |
23 | Correct | 15 ms | 6776 KB | Output is correct |
24 | Correct | 17 ms | 6860 KB | Output is correct |
25 | Correct | 8 ms | 4984 KB | Output is correct |
26 | Correct | 6 ms | 5112 KB | Output is correct |
27 | Correct | 54 ms | 7288 KB | Output is correct |
28 | Correct | 16 ms | 6904 KB | Output is correct |
29 | Correct | 15 ms | 6780 KB | Output is correct |
30 | Correct | 15 ms | 6904 KB | Output is correct |
31 | Correct | 8 ms | 5100 KB | Output is correct |
32 | Correct | 8 ms | 4984 KB | Output is correct |
33 | Correct | 10 ms | 5112 KB | Output is correct |
34 | Correct | 8 ms | 5108 KB | Output is correct |
35 | Correct | 6 ms | 4984 KB | Output is correct |
36 | Correct | 190 ms | 31412 KB | Output is correct |
37 | Correct | 8 ms | 4984 KB | Output is correct |
38 | Correct | 182 ms | 32888 KB | Output is correct |
39 | Correct | 175 ms | 32248 KB | Output is correct |
40 | Correct | 406 ms | 32536 KB | Output is correct |
41 | Correct | 181 ms | 32852 KB | Output is correct |
42 | Correct | 168 ms | 27064 KB | Output is correct |
43 | Correct | 180 ms | 25536 KB | Output is correct |
44 | Correct | 200 ms | 25020 KB | Output is correct |
45 | Correct | 205 ms | 25080 KB | Output is correct |
46 | Correct | 207 ms | 24952 KB | Output is correct |
47 | Correct | 270 ms | 29180 KB | Output is correct |
48 | Correct | 152 ms | 28912 KB | Output is correct |
49 | Correct | 195 ms | 28408 KB | Output is correct |
50 | Correct | 197 ms | 28380 KB | Output is correct |
51 | Correct | 187 ms | 32172 KB | Output is correct |
52 | Correct | 186 ms | 32108 KB | Output is correct |
53 | Correct | 132 ms | 23672 KB | Output is correct |
54 | Correct | 129 ms | 23772 KB | Output is correct |
55 | Correct | 153 ms | 24036 KB | Output is correct |
56 | Correct | 194 ms | 24420 KB | Output is correct |
57 | Correct | 165 ms | 25024 KB | Output is correct |
58 | Correct | 165 ms | 25100 KB | Output is correct |
59 | Correct | 162 ms | 25080 KB | Output is correct |
60 | Correct | 173 ms | 25436 KB | Output is correct |
61 | Correct | 165 ms | 29304 KB | Output is correct |
62 | Correct | 165 ms | 29396 KB | Output is correct |
63 | Correct | 158 ms | 29304 KB | Output is correct |
64 | Correct | 184 ms | 29248 KB | Output is correct |
65 | Correct | 233 ms | 25196 KB | Output is correct |
66 | Correct | 177 ms | 24184 KB | Output is correct |
67 | Correct | 216 ms | 24244 KB | Output is correct |
68 | Correct | 119 ms | 23544 KB | Output is correct |
69 | Correct | 113 ms | 23416 KB | Output is correct |
70 | Correct | 181 ms | 29500 KB | Output is correct |
71 | Correct | 171 ms | 28304 KB | Output is correct |
72 | Correct | 7 ms | 4984 KB | Output is correct |
73 | Correct | 14 ms | 6776 KB | Output is correct |
74 | Correct | 14 ms | 6776 KB | Output is correct |
75 | Correct | 0 ms | 4984 KB | Output is correct |
76 | Correct | 9 ms | 5112 KB | Output is correct |
77 | Correct | 18 ms | 7320 KB | Output is correct |
78 | Correct | 37 ms | 6880 KB | Output is correct |
79 | Correct | 15 ms | 6776 KB | Output is correct |
80 | Correct | 16 ms | 6904 KB | Output is correct |
81 | Correct | 7 ms | 5112 KB | Output is correct |
82 | Correct | 8 ms | 5112 KB | Output is correct |
83 | Correct | 8 ms | 5112 KB | Output is correct |
84 | Correct | 8 ms | 5112 KB | Output is correct |
85 | Correct | 8 ms | 5112 KB | Output is correct |
86 | Correct | 44 ms | 7800 KB | Output is correct |
87 | Correct | 50 ms | 7792 KB | Output is correct |
88 | Correct | 50 ms | 7800 KB | Output is correct |
89 | Correct | 18 ms | 7288 KB | Output is correct |
90 | Correct | 17 ms | 6904 KB | Output is correct |
91 | Correct | 56 ms | 7912 KB | Output is correct |
92 | Correct | 57 ms | 7924 KB | Output is correct |
93 | Correct | 8 ms | 5112 KB | Output is correct |
94 | Correct | 263 ms | 33312 KB | Output is correct |
95 | Correct | 238 ms | 32888 KB | Output is correct |
96 | Correct | 244 ms | 32364 KB | Output is correct |
97 | Correct | 243 ms | 32492 KB | Output is correct |
98 | Correct | 188 ms | 32856 KB | Output is correct |
99 | Correct | 214 ms | 25080 KB | Output is correct |
100 | Correct | 169 ms | 25192 KB | Output is correct |
101 | Correct | 169 ms | 25080 KB | Output is correct |
102 | Correct | 156 ms | 25464 KB | Output is correct |
103 | Correct | 138 ms | 29052 KB | Output is correct |
104 | Correct | 175 ms | 29288 KB | Output is correct |
105 | Correct | 164 ms | 28872 KB | Output is correct |
106 | Correct | 215 ms | 28536 KB | Output is correct |
107 | Correct | 189 ms | 28536 KB | Output is correct |
108 | Correct | 186 ms | 32300 KB | Output is correct |
109 | Correct | 213 ms | 32268 KB | Output is correct |
110 | Correct | 156 ms | 23664 KB | Output is correct |
111 | Correct | 173 ms | 23672 KB | Output is correct |
112 | Correct | 190 ms | 24060 KB | Output is correct |
113 | Correct | 154 ms | 24280 KB | Output is correct |