# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486086 | 2021-11-10T13:57:54 Z | Koosha_mv | Railway (BOI17_railway) | C++14 | 432 ms | 79460 KB |
#include <bits/stdc++.h> using namespace std; #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define Add(x,y) x=(x+y)%mod #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=1e6+99; int n,m,res,k,a[N],sz[N],cnt[N]; vector<int> v[N],g[N]; vector<pair<int,int> > ans; map<int,int> mark; map<pair<int,int>,int> edge; void dfssz(int x,int par){ sz[x]=1; f(i,0,g[x].size()){ if(g[x][i]!=par){ dfssz(g[x][i],x); sz[x]+=sz[g[x][i]]; } } } void dfs1(int x,int par,int fbd){ f(j,0,v[x].size()){ mark[v[x][j]]++; if(mark[v[x][j]]==cnt[v[x][j]]){ res++; } } f(i,0,g[x].size()){ if(g[x][i]!=par && g[x][i]!=fbd){ dfs1(g[x][i],x,fbd); } } } void dfs(int x,int par){ int u=0; f(i,0,g[x].size()){ if(g[x][i]!=par && sz[g[x][i]]>sz[u]){ u=g[x][i]; } } f(i,0,g[x].size()){ if(g[x][i]!=par && g[x][i]!=u){ dfs(g[x][i],x); } } mark.clear(); res=0; if(u>0){ dfs(u,x); } dfs1(x,par,u); //cout<<x<<" : "<<mark.size()<<endl; //cout<<x<<" : "<<endl; //for(auto u : mark){ // cout<<u.F<<" "<<u.S<<endl; //} //cout<<mark.size()<<endl; //cout<<endl; if(mark.size()-res>=k){ ans.pb(mp(x,par)); } } int main(){ cin>>n>>m>>k; f(i,1,n){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); edge[mp(u,v)]=i; edge[mp(v,u)]=i; } f(i,0,m){ int x; cin>>cnt[i]; f(j,0,cnt[i]){ cin>>x; v[x].pb(i); } } dfssz(1,0); dfs(1,0); vector<int> v; cout<<ans.size()<<endl; f(i,0,ans.size()){ v.pb(edge[mp(ans[i].F,ans[i].S)]); } sort(v.begin(),v.end()); f(i,0,v.size()) cout<<v[i]<<" "; } /* 6 3 2 1 3 2 3 3 4 6 4 4 5 4 1 3 2 5 2 6 3 2 3 2 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 47180 KB | Output is correct |
2 | Correct | 42 ms | 48844 KB | Output is correct |
3 | Correct | 39 ms | 48928 KB | Output is correct |
4 | Correct | 21 ms | 47184 KB | Output is correct |
5 | Correct | 21 ms | 47276 KB | Output is correct |
6 | Correct | 33 ms | 49488 KB | Output is correct |
7 | Correct | 33 ms | 49068 KB | Output is correct |
8 | Correct | 31 ms | 49112 KB | Output is correct |
9 | Correct | 33 ms | 49072 KB | Output is correct |
10 | Correct | 21 ms | 47220 KB | Output is correct |
11 | Correct | 21 ms | 47184 KB | Output is correct |
12 | Correct | 22 ms | 47272 KB | Output is correct |
13 | Correct | 21 ms | 47152 KB | Output is correct |
14 | Correct | 21 ms | 47184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 47180 KB | Output is correct |
2 | Correct | 42 ms | 48844 KB | Output is correct |
3 | Correct | 39 ms | 48928 KB | Output is correct |
4 | Correct | 21 ms | 47184 KB | Output is correct |
5 | Correct | 21 ms | 47276 KB | Output is correct |
6 | Correct | 33 ms | 49488 KB | Output is correct |
7 | Correct | 33 ms | 49068 KB | Output is correct |
8 | Correct | 31 ms | 49112 KB | Output is correct |
9 | Correct | 33 ms | 49072 KB | Output is correct |
10 | Correct | 21 ms | 47220 KB | Output is correct |
11 | Correct | 21 ms | 47184 KB | Output is correct |
12 | Correct | 22 ms | 47272 KB | Output is correct |
13 | Correct | 21 ms | 47152 KB | Output is correct |
14 | Correct | 21 ms | 47184 KB | Output is correct |
15 | Correct | 75 ms | 49992 KB | Output is correct |
16 | Correct | 80 ms | 50096 KB | Output is correct |
17 | Correct | 79 ms | 50124 KB | Output is correct |
18 | Correct | 37 ms | 49488 KB | Output is correct |
19 | Correct | 34 ms | 49104 KB | Output is correct |
20 | Correct | 76 ms | 50376 KB | Output is correct |
21 | Correct | 71 ms | 50236 KB | Output is correct |
22 | Correct | 26 ms | 47184 KB | Output is correct |
23 | Correct | 35 ms | 48940 KB | Output is correct |
24 | Correct | 34 ms | 48976 KB | Output is correct |
25 | Correct | 25 ms | 47264 KB | Output is correct |
26 | Correct | 22 ms | 47184 KB | Output is correct |
27 | Correct | 34 ms | 49560 KB | Output is correct |
28 | Correct | 33 ms | 49060 KB | Output is correct |
29 | Correct | 31 ms | 49116 KB | Output is correct |
30 | Correct | 34 ms | 49020 KB | Output is correct |
31 | Correct | 21 ms | 47224 KB | Output is correct |
32 | Correct | 22 ms | 47332 KB | Output is correct |
33 | Correct | 21 ms | 47184 KB | Output is correct |
34 | Correct | 21 ms | 47184 KB | Output is correct |
35 | Correct | 21 ms | 47184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 218 ms | 77496 KB | Output is correct |
2 | Correct | 21 ms | 47180 KB | Output is correct |
3 | Correct | 216 ms | 76816 KB | Output is correct |
4 | Correct | 222 ms | 75620 KB | Output is correct |
5 | Correct | 195 ms | 75368 KB | Output is correct |
6 | Correct | 220 ms | 75336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 232 ms | 70324 KB | Output is correct |
2 | Correct | 290 ms | 66888 KB | Output is correct |
3 | Correct | 359 ms | 66680 KB | Output is correct |
4 | Correct | 374 ms | 68376 KB | Output is correct |
5 | Correct | 383 ms | 68428 KB | Output is correct |
6 | Correct | 234 ms | 72520 KB | Output is correct |
7 | Correct | 233 ms | 72248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 232 ms | 70324 KB | Output is correct |
2 | Correct | 290 ms | 66888 KB | Output is correct |
3 | Correct | 359 ms | 66680 KB | Output is correct |
4 | Correct | 374 ms | 68376 KB | Output is correct |
5 | Correct | 383 ms | 68428 KB | Output is correct |
6 | Correct | 234 ms | 72520 KB | Output is correct |
7 | Correct | 233 ms | 72248 KB | Output is correct |
8 | Correct | 237 ms | 72140 KB | Output is correct |
9 | Correct | 268 ms | 72116 KB | Output is correct |
10 | Correct | 189 ms | 76996 KB | Output is correct |
11 | Correct | 191 ms | 76860 KB | Output is correct |
12 | Correct | 190 ms | 67084 KB | Output is correct |
13 | Correct | 191 ms | 67056 KB | Output is correct |
14 | Correct | 316 ms | 66036 KB | Output is correct |
15 | Correct | 288 ms | 66060 KB | Output is correct |
16 | Correct | 383 ms | 68424 KB | Output is correct |
17 | Correct | 383 ms | 68380 KB | Output is correct |
18 | Correct | 399 ms | 68424 KB | Output is correct |
19 | Correct | 296 ms | 68616 KB | Output is correct |
20 | Correct | 239 ms | 72780 KB | Output is correct |
21 | Correct | 250 ms | 73040 KB | Output is correct |
22 | Correct | 242 ms | 72792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 47180 KB | Output is correct |
2 | Correct | 42 ms | 48844 KB | Output is correct |
3 | Correct | 39 ms | 48928 KB | Output is correct |
4 | Correct | 21 ms | 47184 KB | Output is correct |
5 | Correct | 21 ms | 47276 KB | Output is correct |
6 | Correct | 33 ms | 49488 KB | Output is correct |
7 | Correct | 33 ms | 49068 KB | Output is correct |
8 | Correct | 31 ms | 49112 KB | Output is correct |
9 | Correct | 33 ms | 49072 KB | Output is correct |
10 | Correct | 21 ms | 47220 KB | Output is correct |
11 | Correct | 21 ms | 47184 KB | Output is correct |
12 | Correct | 22 ms | 47272 KB | Output is correct |
13 | Correct | 21 ms | 47152 KB | Output is correct |
14 | Correct | 21 ms | 47184 KB | Output is correct |
15 | Correct | 75 ms | 49992 KB | Output is correct |
16 | Correct | 80 ms | 50096 KB | Output is correct |
17 | Correct | 79 ms | 50124 KB | Output is correct |
18 | Correct | 37 ms | 49488 KB | Output is correct |
19 | Correct | 34 ms | 49104 KB | Output is correct |
20 | Correct | 76 ms | 50376 KB | Output is correct |
21 | Correct | 71 ms | 50236 KB | Output is correct |
22 | Correct | 26 ms | 47184 KB | Output is correct |
23 | Correct | 35 ms | 48940 KB | Output is correct |
24 | Correct | 34 ms | 48976 KB | Output is correct |
25 | Correct | 25 ms | 47264 KB | Output is correct |
26 | Correct | 22 ms | 47184 KB | Output is correct |
27 | Correct | 34 ms | 49560 KB | Output is correct |
28 | Correct | 33 ms | 49060 KB | Output is correct |
29 | Correct | 31 ms | 49116 KB | Output is correct |
30 | Correct | 34 ms | 49020 KB | Output is correct |
31 | Correct | 21 ms | 47224 KB | Output is correct |
32 | Correct | 22 ms | 47332 KB | Output is correct |
33 | Correct | 21 ms | 47184 KB | Output is correct |
34 | Correct | 21 ms | 47184 KB | Output is correct |
35 | Correct | 21 ms | 47184 KB | Output is correct |
36 | Correct | 218 ms | 77496 KB | Output is correct |
37 | Correct | 21 ms | 47180 KB | Output is correct |
38 | Correct | 216 ms | 76816 KB | Output is correct |
39 | Correct | 222 ms | 75620 KB | Output is correct |
40 | Correct | 195 ms | 75368 KB | Output is correct |
41 | Correct | 220 ms | 75336 KB | Output is correct |
42 | Correct | 232 ms | 70324 KB | Output is correct |
43 | Correct | 290 ms | 66888 KB | Output is correct |
44 | Correct | 359 ms | 66680 KB | Output is correct |
45 | Correct | 374 ms | 68376 KB | Output is correct |
46 | Correct | 383 ms | 68428 KB | Output is correct |
47 | Correct | 234 ms | 72520 KB | Output is correct |
48 | Correct | 233 ms | 72248 KB | Output is correct |
49 | Correct | 237 ms | 72140 KB | Output is correct |
50 | Correct | 268 ms | 72116 KB | Output is correct |
51 | Correct | 189 ms | 76996 KB | Output is correct |
52 | Correct | 191 ms | 76860 KB | Output is correct |
53 | Correct | 190 ms | 67084 KB | Output is correct |
54 | Correct | 191 ms | 67056 KB | Output is correct |
55 | Correct | 316 ms | 66036 KB | Output is correct |
56 | Correct | 288 ms | 66060 KB | Output is correct |
57 | Correct | 383 ms | 68424 KB | Output is correct |
58 | Correct | 383 ms | 68380 KB | Output is correct |
59 | Correct | 399 ms | 68424 KB | Output is correct |
60 | Correct | 296 ms | 68616 KB | Output is correct |
61 | Correct | 239 ms | 72780 KB | Output is correct |
62 | Correct | 250 ms | 73040 KB | Output is correct |
63 | Correct | 242 ms | 72792 KB | Output is correct |
64 | Correct | 254 ms | 73304 KB | Output is correct |
65 | Correct | 387 ms | 69676 KB | Output is correct |
66 | Correct | 341 ms | 67372 KB | Output is correct |
67 | Correct | 309 ms | 67212 KB | Output is correct |
68 | Correct | 197 ms | 66376 KB | Output is correct |
69 | Correct | 206 ms | 66400 KB | Output is correct |
70 | Correct | 255 ms | 73976 KB | Output is correct |
71 | Correct | 231 ms | 71880 KB | Output is correct |
72 | Correct | 22 ms | 47268 KB | Output is correct |
73 | Correct | 34 ms | 48896 KB | Output is correct |
74 | Correct | 34 ms | 48976 KB | Output is correct |
75 | Correct | 24 ms | 47184 KB | Output is correct |
76 | Correct | 20 ms | 47276 KB | Output is correct |
77 | Correct | 35 ms | 49592 KB | Output is correct |
78 | Correct | 34 ms | 49128 KB | Output is correct |
79 | Correct | 32 ms | 49072 KB | Output is correct |
80 | Correct | 35 ms | 49104 KB | Output is correct |
81 | Correct | 22 ms | 47188 KB | Output is correct |
82 | Correct | 21 ms | 47184 KB | Output is correct |
83 | Correct | 24 ms | 47236 KB | Output is correct |
84 | Correct | 22 ms | 47184 KB | Output is correct |
85 | Correct | 21 ms | 47184 KB | Output is correct |
86 | Correct | 79 ms | 50116 KB | Output is correct |
87 | Correct | 84 ms | 50136 KB | Output is correct |
88 | Correct | 82 ms | 50120 KB | Output is correct |
89 | Correct | 35 ms | 49480 KB | Output is correct |
90 | Correct | 34 ms | 49100 KB | Output is correct |
91 | Correct | 74 ms | 50348 KB | Output is correct |
92 | Correct | 77 ms | 50388 KB | Output is correct |
93 | Correct | 22 ms | 47276 KB | Output is correct |
94 | Correct | 226 ms | 79460 KB | Output is correct |
95 | Correct | 210 ms | 78528 KB | Output is correct |
96 | Correct | 199 ms | 77384 KB | Output is correct |
97 | Correct | 204 ms | 77164 KB | Output is correct |
98 | Correct | 207 ms | 77284 KB | Output is correct |
99 | Correct | 364 ms | 68424 KB | Output is correct |
100 | Correct | 386 ms | 68448 KB | Output is correct |
101 | Correct | 432 ms | 68348 KB | Output is correct |
102 | Correct | 301 ms | 68696 KB | Output is correct |
103 | Correct | 234 ms | 72308 KB | Output is correct |
104 | Correct | 252 ms | 73028 KB | Output is correct |
105 | Correct | 237 ms | 72264 KB | Output is correct |
106 | Correct | 235 ms | 72300 KB | Output is correct |
107 | Correct | 230 ms | 71980 KB | Output is correct |
108 | Correct | 192 ms | 76868 KB | Output is correct |
109 | Correct | 185 ms | 76840 KB | Output is correct |
110 | Correct | 193 ms | 67016 KB | Output is correct |
111 | Correct | 202 ms | 67192 KB | Output is correct |
112 | Correct | 312 ms | 65996 KB | Output is correct |
113 | Correct | 306 ms | 65940 KB | Output is correct |