# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
245198 | 2020-07-05T17:21:24 Z | m3r8 | Railway (BOI17_railway) | C++14 | 299 ms | 49756 KB |
#include <stdio.h> #include <set> #include <vector> #include <algorithm> #define N 100100 std::vector<int> adj[N]; std::vector<int> lll[N]; int num[N]; int sst[N]; std::vector<int> erg; std::set<int> avi[N]; std::vector<int> st[N]; std::vector<int> en[N]; int cnt = 1; int k; int in[N]; int out[N]; int pre[N][20]; int bef(int v, int u){ if(v == 0)return 1; if(u == 0)return 0; return in[u] >= in[v] && out[u] <= out[v]; }; int lca(int v, int u){ if(v == u)return v; if(bef(v,u))return v; if(bef(u,v))return u; int akt = v; for(int i = 19;i>=0;i--){ if(!bef(pre[akt][i],u)){ akt = pre[akt][i]; }; }; return pre[akt][0]; }; void dfs(int v, int p){ in[v] = cnt++; pre[v][0] = p; for(int i = 1;i<20;i++){ pre[v][i] = pre[pre[v][i-1]][i-1]; }; for(int i = 0;i<adj[v].size();i++){ int u = adj[v][i]; if(u != p){ dfs(u,v); }else{ num[v] = lll[v][i]; }; }; out[v] = cnt-1; }; void solve(int v, int p){ int mx = 0; int mxi = 0; for(int i = 0;i<adj[v].size();i++){ int u = adj[v][i]; if(u != p){ solve(u,v); if(avi[sst[u]].size() >= mx){ mx = avi[sst[u]].size(); mxi = i; }; }; }; sst[v] = v; if(adj[v].size() > 1)sst[v] = sst[adj[v][mxi]]; for(int i = 0;i<adj[v].size();i++){ int u = adj[v][i]; if(u != p){ if(sst[u] != sst[v]){ for(auto tmp: avi[sst[u]]){ avi[sst[v]].insert(tmp); }; }; }; }; for(auto i: st[v]){ avi[sst[v]].insert(i); }; for(auto i: en[v])avi[sst[v]].erase(i); if(avi[sst[v]].size() >= k){ erg.push_back(num[v]); }; for(auto i: adj[v]){ if(i != p && sst[i] != sst[v])avi[sst[i]].clear(); }; }; int main(void){ int n,m; scanf("%d %d %d",&n,&m,&k); int a,b; for(int i = 1;i<n;i++){ scanf("%d %d",&a,&b); adj[a].push_back(b); adj[b].push_back(a); lll[a].push_back(i); lll[b].push_back(i); }; dfs(1,0); for(int i = 1;i<=m;i++){ int cc; int s; scanf("%d",&cc); int lcs = 0; for(int j = 0;j<cc;j++){ scanf("%d",&s); st[s].push_back(i); if(!lcs)lcs = s; else lcs = lca(lcs,s); }; en[lcs].push_back(i); }; /* for(int i = 1;i<=n;i++){ printf("start %d: ",i); for(auto j: st[i])printf("%d ",j); puts(""); printf("end %d: ",i); for(auto j: en[i])printf("%d ",j); puts(""); }; */ solve(1,0); printf("%d\n",erg.size()); std::sort(erg.begin(),erg.end()); for(int i = 0;i<erg.size();i++){ printf("%d ",erg[i]); }; puts(""); return 0; };
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14464 KB | Output is correct |
2 | Correct | 21 ms | 16256 KB | Output is correct |
3 | Correct | 21 ms | 16128 KB | Output is correct |
4 | Correct | 13 ms | 14464 KB | Output is correct |
5 | Correct | 14 ms | 14464 KB | Output is correct |
6 | Correct | 22 ms | 16896 KB | Output is correct |
7 | Correct | 21 ms | 16256 KB | Output is correct |
8 | Correct | 20 ms | 16384 KB | Output is correct |
9 | Correct | 22 ms | 16256 KB | Output is correct |
10 | Correct | 13 ms | 14464 KB | Output is correct |
11 | Correct | 13 ms | 14464 KB | Output is correct |
12 | Correct | 14 ms | 14464 KB | Output is correct |
13 | Correct | 12 ms | 14464 KB | Output is correct |
14 | Correct | 13 ms | 14464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14464 KB | Output is correct |
2 | Correct | 21 ms | 16256 KB | Output is correct |
3 | Correct | 21 ms | 16128 KB | Output is correct |
4 | Correct | 13 ms | 14464 KB | Output is correct |
5 | Correct | 14 ms | 14464 KB | Output is correct |
6 | Correct | 22 ms | 16896 KB | Output is correct |
7 | Correct | 21 ms | 16256 KB | Output is correct |
8 | Correct | 20 ms | 16384 KB | Output is correct |
9 | Correct | 22 ms | 16256 KB | Output is correct |
10 | Correct | 13 ms | 14464 KB | Output is correct |
11 | Correct | 13 ms | 14464 KB | Output is correct |
12 | Correct | 14 ms | 14464 KB | Output is correct |
13 | Correct | 12 ms | 14464 KB | Output is correct |
14 | Correct | 13 ms | 14464 KB | Output is correct |
15 | Correct | 49 ms | 17148 KB | Output is correct |
16 | Correct | 50 ms | 17400 KB | Output is correct |
17 | Correct | 50 ms | 17400 KB | Output is correct |
18 | Correct | 23 ms | 16896 KB | Output is correct |
19 | Correct | 22 ms | 16384 KB | Output is correct |
20 | Correct | 58 ms | 22140 KB | Output is correct |
21 | Correct | 55 ms | 19072 KB | Output is correct |
22 | Correct | 13 ms | 14464 KB | Output is correct |
23 | Correct | 21 ms | 16128 KB | Output is correct |
24 | Correct | 21 ms | 16128 KB | Output is correct |
25 | Correct | 13 ms | 14464 KB | Output is correct |
26 | Correct | 13 ms | 14464 KB | Output is correct |
27 | Correct | 22 ms | 16896 KB | Output is correct |
28 | Correct | 21 ms | 16256 KB | Output is correct |
29 | Correct | 20 ms | 16384 KB | Output is correct |
30 | Correct | 22 ms | 16384 KB | Output is correct |
31 | Correct | 13 ms | 14464 KB | Output is correct |
32 | Correct | 13 ms | 14464 KB | Output is correct |
33 | Correct | 13 ms | 14464 KB | Output is correct |
34 | Correct | 13 ms | 14464 KB | Output is correct |
35 | Correct | 13 ms | 14464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 182 ms | 47984 KB | Output is correct |
2 | Correct | 13 ms | 14464 KB | Output is correct |
3 | Correct | 182 ms | 49268 KB | Output is correct |
4 | Correct | 179 ms | 48936 KB | Output is correct |
5 | Correct | 151 ms | 47792 KB | Output is correct |
6 | Correct | 148 ms | 47596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 172 ms | 39928 KB | Output is correct |
2 | Correct | 211 ms | 36276 KB | Output is correct |
3 | Correct | 225 ms | 37492 KB | Output is correct |
4 | Correct | 217 ms | 37748 KB | Output is correct |
5 | Correct | 227 ms | 37876 KB | Output is correct |
6 | Correct | 175 ms | 41592 KB | Output is correct |
7 | Correct | 168 ms | 41428 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 172 ms | 39928 KB | Output is correct |
2 | Correct | 211 ms | 36276 KB | Output is correct |
3 | Correct | 225 ms | 37492 KB | Output is correct |
4 | Correct | 217 ms | 37748 KB | Output is correct |
5 | Correct | 227 ms | 37876 KB | Output is correct |
6 | Correct | 175 ms | 41592 KB | Output is correct |
7 | Correct | 168 ms | 41428 KB | Output is correct |
8 | Correct | 171 ms | 41208 KB | Output is correct |
9 | Correct | 167 ms | 41208 KB | Output is correct |
10 | Correct | 138 ms | 47348 KB | Output is correct |
11 | Correct | 136 ms | 47348 KB | Output is correct |
12 | Correct | 131 ms | 34808 KB | Output is correct |
13 | Correct | 131 ms | 34876 KB | Output is correct |
14 | Correct | 200 ms | 33912 KB | Output is correct |
15 | Correct | 212 ms | 33784 KB | Output is correct |
16 | Correct | 241 ms | 38260 KB | Output is correct |
17 | Correct | 226 ms | 37748 KB | Output is correct |
18 | Correct | 215 ms | 37748 KB | Output is correct |
19 | Correct | 211 ms | 36216 KB | Output is correct |
20 | Correct | 171 ms | 41868 KB | Output is correct |
21 | Correct | 178 ms | 42096 KB | Output is correct |
22 | Correct | 173 ms | 41848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14464 KB | Output is correct |
2 | Correct | 21 ms | 16256 KB | Output is correct |
3 | Correct | 21 ms | 16128 KB | Output is correct |
4 | Correct | 13 ms | 14464 KB | Output is correct |
5 | Correct | 14 ms | 14464 KB | Output is correct |
6 | Correct | 22 ms | 16896 KB | Output is correct |
7 | Correct | 21 ms | 16256 KB | Output is correct |
8 | Correct | 20 ms | 16384 KB | Output is correct |
9 | Correct | 22 ms | 16256 KB | Output is correct |
10 | Correct | 13 ms | 14464 KB | Output is correct |
11 | Correct | 13 ms | 14464 KB | Output is correct |
12 | Correct | 14 ms | 14464 KB | Output is correct |
13 | Correct | 12 ms | 14464 KB | Output is correct |
14 | Correct | 13 ms | 14464 KB | Output is correct |
15 | Correct | 49 ms | 17148 KB | Output is correct |
16 | Correct | 50 ms | 17400 KB | Output is correct |
17 | Correct | 50 ms | 17400 KB | Output is correct |
18 | Correct | 23 ms | 16896 KB | Output is correct |
19 | Correct | 22 ms | 16384 KB | Output is correct |
20 | Correct | 58 ms | 22140 KB | Output is correct |
21 | Correct | 55 ms | 19072 KB | Output is correct |
22 | Correct | 13 ms | 14464 KB | Output is correct |
23 | Correct | 21 ms | 16128 KB | Output is correct |
24 | Correct | 21 ms | 16128 KB | Output is correct |
25 | Correct | 13 ms | 14464 KB | Output is correct |
26 | Correct | 13 ms | 14464 KB | Output is correct |
27 | Correct | 22 ms | 16896 KB | Output is correct |
28 | Correct | 21 ms | 16256 KB | Output is correct |
29 | Correct | 20 ms | 16384 KB | Output is correct |
30 | Correct | 22 ms | 16384 KB | Output is correct |
31 | Correct | 13 ms | 14464 KB | Output is correct |
32 | Correct | 13 ms | 14464 KB | Output is correct |
33 | Correct | 13 ms | 14464 KB | Output is correct |
34 | Correct | 13 ms | 14464 KB | Output is correct |
35 | Correct | 13 ms | 14464 KB | Output is correct |
36 | Correct | 182 ms | 47984 KB | Output is correct |
37 | Correct | 13 ms | 14464 KB | Output is correct |
38 | Correct | 182 ms | 49268 KB | Output is correct |
39 | Correct | 179 ms | 48936 KB | Output is correct |
40 | Correct | 151 ms | 47792 KB | Output is correct |
41 | Correct | 148 ms | 47596 KB | Output is correct |
42 | Correct | 172 ms | 39928 KB | Output is correct |
43 | Correct | 211 ms | 36276 KB | Output is correct |
44 | Correct | 225 ms | 37492 KB | Output is correct |
45 | Correct | 217 ms | 37748 KB | Output is correct |
46 | Correct | 227 ms | 37876 KB | Output is correct |
47 | Correct | 175 ms | 41592 KB | Output is correct |
48 | Correct | 168 ms | 41428 KB | Output is correct |
49 | Correct | 171 ms | 41208 KB | Output is correct |
50 | Correct | 167 ms | 41208 KB | Output is correct |
51 | Correct | 138 ms | 47348 KB | Output is correct |
52 | Correct | 136 ms | 47348 KB | Output is correct |
53 | Correct | 131 ms | 34808 KB | Output is correct |
54 | Correct | 131 ms | 34876 KB | Output is correct |
55 | Correct | 200 ms | 33912 KB | Output is correct |
56 | Correct | 212 ms | 33784 KB | Output is correct |
57 | Correct | 241 ms | 38260 KB | Output is correct |
58 | Correct | 226 ms | 37748 KB | Output is correct |
59 | Correct | 215 ms | 37748 KB | Output is correct |
60 | Correct | 211 ms | 36216 KB | Output is correct |
61 | Correct | 171 ms | 41868 KB | Output is correct |
62 | Correct | 178 ms | 42096 KB | Output is correct |
63 | Correct | 173 ms | 41848 KB | Output is correct |
64 | Correct | 196 ms | 41848 KB | Output is correct |
65 | Correct | 299 ms | 37496 KB | Output is correct |
66 | Correct | 234 ms | 35448 KB | Output is correct |
67 | Correct | 220 ms | 34808 KB | Output is correct |
68 | Correct | 138 ms | 33784 KB | Output is correct |
69 | Correct | 134 ms | 33820 KB | Output is correct |
70 | Correct | 195 ms | 42744 KB | Output is correct |
71 | Correct | 169 ms | 41080 KB | Output is correct |
72 | Correct | 13 ms | 14464 KB | Output is correct |
73 | Correct | 21 ms | 16128 KB | Output is correct |
74 | Correct | 21 ms | 16128 KB | Output is correct |
75 | Correct | 14 ms | 14464 KB | Output is correct |
76 | Correct | 14 ms | 14464 KB | Output is correct |
77 | Correct | 22 ms | 16896 KB | Output is correct |
78 | Correct | 21 ms | 16256 KB | Output is correct |
79 | Correct | 19 ms | 16384 KB | Output is correct |
80 | Correct | 24 ms | 16384 KB | Output is correct |
81 | Correct | 14 ms | 14464 KB | Output is correct |
82 | Correct | 13 ms | 14464 KB | Output is correct |
83 | Correct | 13 ms | 14464 KB | Output is correct |
84 | Correct | 13 ms | 14464 KB | Output is correct |
85 | Correct | 13 ms | 14464 KB | Output is correct |
86 | Correct | 52 ms | 17276 KB | Output is correct |
87 | Correct | 50 ms | 17400 KB | Output is correct |
88 | Correct | 55 ms | 17400 KB | Output is correct |
89 | Correct | 23 ms | 16896 KB | Output is correct |
90 | Correct | 24 ms | 16384 KB | Output is correct |
91 | Correct | 57 ms | 22136 KB | Output is correct |
92 | Correct | 54 ms | 19064 KB | Output is correct |
93 | Correct | 15 ms | 14464 KB | Output is correct |
94 | Correct | 193 ms | 49756 KB | Output is correct |
95 | Correct | 184 ms | 49268 KB | Output is correct |
96 | Correct | 177 ms | 48760 KB | Output is correct |
97 | Correct | 159 ms | 47892 KB | Output is correct |
98 | Correct | 155 ms | 47648 KB | Output is correct |
99 | Correct | 246 ms | 39028 KB | Output is correct |
100 | Correct | 237 ms | 38260 KB | Output is correct |
101 | Correct | 258 ms | 37876 KB | Output is correct |
102 | Correct | 207 ms | 36088 KB | Output is correct |
103 | Correct | 170 ms | 41592 KB | Output is correct |
104 | Correct | 189 ms | 41844 KB | Output is correct |
105 | Correct | 179 ms | 41468 KB | Output is correct |
106 | Correct | 186 ms | 41336 KB | Output is correct |
107 | Correct | 163 ms | 41208 KB | Output is correct |
108 | Correct | 135 ms | 47348 KB | Output is correct |
109 | Correct | 138 ms | 47348 KB | Output is correct |
110 | Correct | 145 ms | 34808 KB | Output is correct |
111 | Correct | 133 ms | 34808 KB | Output is correct |
112 | Correct | 217 ms | 33764 KB | Output is correct |
113 | Correct | 203 ms | 33784 KB | Output is correct |