# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
129636 |
2019-07-12T20:32:45 Z |
luciocf |
Railway (BOI17_railway) |
C++14 |
|
542 ms |
50032 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef pair<int, int> pii;
int chain[maxn], head[maxn], ind[maxn], back[maxn], cc, pp;
int sz[maxn], nivel[maxn], pai[maxn], n;
int freq[maxn], mark[maxn], aux;
vector<int> grafo[maxn], tree[4*maxn];
void dfs(int u, int p)
{
sz[u] = 1;
for (auto v: grafo[u])
{
if (v == p) continue;
nivel[v] = nivel[u]+1, pai[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u)
{
if (!head[cc]) head[cc] = u;
chain[u] = cc, ind[u] = ++pp, back[pp] = u;
int maior = -1, child = -1;
for (auto v: grafo[u])
if (v != pai[u] && sz[v] > maior)
maior = sz[v], child = v;
if (child != -1) hld(child);
for (auto v: grafo[u])
if (v != pai[u] && v != child)
cc++, hld(v);
}
int lca(int u, int v)
{
while (chain[u] != chain[v])
{
if (nivel[head[chain[u]]] > nivel[head[chain[v]]])
u = pai[head[chain[u]]];
else
v = pai[head[chain[v]]];
}
return (nivel[u] > nivel[v] ? v : u);
}
void upd(int node, int l, int r, int a, int b, int v)
{
if (l > b || r < a) return;
if (l >= a && r <= b)
{
tree[node].push_back(v);
return;
}
int mid = (l+r)>>1;
upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);
}
void upd_path(int u, int v, int it)
{
while (true)
{
if (chain[u] == chain[v])
{
if (u != v) upd(1, 1, n, ind[v]+1, ind[u], it);
return;
}
upd(1, 1, n, ind[head[chain[u]]], ind[u], it);
u = pai[head[chain[u]]];
}
}
void solve(int node, int l, int r)
{
for (auto x: tree[node])
{
if (!mark[x]) aux++;
mark[x]++;
}
if (l == r) freq[back[l]] = aux;
if (l != r)
{
int mid = (l+r)>>1;
solve(2*node, l, mid); solve(2*node+1, mid+1, r);
}
for (auto x: tree[node])
{
mark[x]--;
if (!mark[x]) aux--;
}
}
int main(void)
{
ios::sync_with_stdio(false); cin.tie(0);
int m, k;
cin >> n >> m >> k;
map<pii, int> mp;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
grafo[u].push_back(v); grafo[v].push_back(u);
mp[{u, v}] = mp[{v, u}] = i;
}
dfs(1, 0);
hld(1);
for (int i = 1; i <= m; i++)
{
int s, u;
cin >> s >> u;
for (int j = 2; j <= s; j++)
{
int v, low;
cin >> v;
low = lca(u, v);
upd_path(u, low, i); upd_path(v, low, i);
}
}
solve(1, 1, n);
int qtd = 0;
vector<int> ans;
for (int i = 1; i <= n; i++)
{
if (freq[i] >= k)
{
qtd++;
ans.push_back(mp[{i, pai[i]}]);
}
}
sort(ans.begin(), ans.end());
cout << qtd << "\n";
if (qtd)
{
cout << ans[0];
for (int i = 1; i < ans.size(); i++)
cout << " " << ans[i];
cout << "\n";
}
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:172:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < ans.size(); i++)
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12152 KB |
Output is correct |
2 |
Correct |
26 ms |
14200 KB |
Output is correct |
3 |
Correct |
26 ms |
14200 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
12 ms |
12152 KB |
Output is correct |
6 |
Correct |
25 ms |
14712 KB |
Output is correct |
7 |
Correct |
26 ms |
14328 KB |
Output is correct |
8 |
Correct |
23 ms |
14200 KB |
Output is correct |
9 |
Correct |
25 ms |
14200 KB |
Output is correct |
10 |
Correct |
12 ms |
12152 KB |
Output is correct |
11 |
Correct |
12 ms |
12152 KB |
Output is correct |
12 |
Correct |
12 ms |
12152 KB |
Output is correct |
13 |
Correct |
12 ms |
12152 KB |
Output is correct |
14 |
Correct |
13 ms |
12152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12152 KB |
Output is correct |
2 |
Correct |
26 ms |
14200 KB |
Output is correct |
3 |
Correct |
26 ms |
14200 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
12 ms |
12152 KB |
Output is correct |
6 |
Correct |
25 ms |
14712 KB |
Output is correct |
7 |
Correct |
26 ms |
14328 KB |
Output is correct |
8 |
Correct |
23 ms |
14200 KB |
Output is correct |
9 |
Correct |
25 ms |
14200 KB |
Output is correct |
10 |
Correct |
12 ms |
12152 KB |
Output is correct |
11 |
Correct |
12 ms |
12152 KB |
Output is correct |
12 |
Correct |
12 ms |
12152 KB |
Output is correct |
13 |
Correct |
12 ms |
12152 KB |
Output is correct |
14 |
Correct |
13 ms |
12152 KB |
Output is correct |
15 |
Correct |
109 ms |
17520 KB |
Output is correct |
16 |
Correct |
121 ms |
17544 KB |
Output is correct |
17 |
Correct |
126 ms |
17544 KB |
Output is correct |
18 |
Correct |
26 ms |
14584 KB |
Output is correct |
19 |
Correct |
32 ms |
14456 KB |
Output is correct |
20 |
Correct |
79 ms |
16120 KB |
Output is correct |
21 |
Correct |
109 ms |
16240 KB |
Output is correct |
22 |
Correct |
12 ms |
12152 KB |
Output is correct |
23 |
Correct |
26 ms |
14200 KB |
Output is correct |
24 |
Correct |
34 ms |
14172 KB |
Output is correct |
25 |
Correct |
12 ms |
12152 KB |
Output is correct |
26 |
Correct |
13 ms |
12152 KB |
Output is correct |
27 |
Correct |
27 ms |
14632 KB |
Output is correct |
28 |
Correct |
26 ms |
14328 KB |
Output is correct |
29 |
Correct |
23 ms |
14200 KB |
Output is correct |
30 |
Correct |
24 ms |
14200 KB |
Output is correct |
31 |
Correct |
12 ms |
12152 KB |
Output is correct |
32 |
Correct |
13 ms |
12152 KB |
Output is correct |
33 |
Correct |
12 ms |
12152 KB |
Output is correct |
34 |
Correct |
12 ms |
12152 KB |
Output is correct |
35 |
Correct |
12 ms |
12152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
46120 KB |
Output is correct |
2 |
Correct |
13 ms |
12152 KB |
Output is correct |
3 |
Correct |
303 ms |
45792 KB |
Output is correct |
4 |
Correct |
267 ms |
45032 KB |
Output is correct |
5 |
Correct |
342 ms |
48804 KB |
Output is correct |
6 |
Correct |
334 ms |
50032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
233 ms |
39288 KB |
Output is correct |
2 |
Correct |
276 ms |
35940 KB |
Output is correct |
3 |
Correct |
312 ms |
35492 KB |
Output is correct |
4 |
Correct |
331 ms |
36168 KB |
Output is correct |
5 |
Correct |
397 ms |
35456 KB |
Output is correct |
6 |
Correct |
267 ms |
39580 KB |
Output is correct |
7 |
Correct |
268 ms |
39416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
233 ms |
39288 KB |
Output is correct |
2 |
Correct |
276 ms |
35940 KB |
Output is correct |
3 |
Correct |
312 ms |
35492 KB |
Output is correct |
4 |
Correct |
331 ms |
36168 KB |
Output is correct |
5 |
Correct |
397 ms |
35456 KB |
Output is correct |
6 |
Correct |
267 ms |
39580 KB |
Output is correct |
7 |
Correct |
268 ms |
39416 KB |
Output is correct |
8 |
Correct |
293 ms |
42912 KB |
Output is correct |
9 |
Correct |
292 ms |
43164 KB |
Output is correct |
10 |
Correct |
355 ms |
49360 KB |
Output is correct |
11 |
Correct |
340 ms |
49076 KB |
Output is correct |
12 |
Correct |
268 ms |
35952 KB |
Output is correct |
13 |
Correct |
336 ms |
36228 KB |
Output is correct |
14 |
Correct |
387 ms |
37996 KB |
Output is correct |
15 |
Correct |
481 ms |
37740 KB |
Output is correct |
16 |
Correct |
344 ms |
36116 KB |
Output is correct |
17 |
Correct |
355 ms |
35680 KB |
Output is correct |
18 |
Correct |
309 ms |
35808 KB |
Output is correct |
19 |
Correct |
290 ms |
36256 KB |
Output is correct |
20 |
Correct |
263 ms |
40536 KB |
Output is correct |
21 |
Correct |
241 ms |
40164 KB |
Output is correct |
22 |
Correct |
254 ms |
40548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12152 KB |
Output is correct |
2 |
Correct |
26 ms |
14200 KB |
Output is correct |
3 |
Correct |
26 ms |
14200 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
12 ms |
12152 KB |
Output is correct |
6 |
Correct |
25 ms |
14712 KB |
Output is correct |
7 |
Correct |
26 ms |
14328 KB |
Output is correct |
8 |
Correct |
23 ms |
14200 KB |
Output is correct |
9 |
Correct |
25 ms |
14200 KB |
Output is correct |
10 |
Correct |
12 ms |
12152 KB |
Output is correct |
11 |
Correct |
12 ms |
12152 KB |
Output is correct |
12 |
Correct |
12 ms |
12152 KB |
Output is correct |
13 |
Correct |
12 ms |
12152 KB |
Output is correct |
14 |
Correct |
13 ms |
12152 KB |
Output is correct |
15 |
Correct |
109 ms |
17520 KB |
Output is correct |
16 |
Correct |
121 ms |
17544 KB |
Output is correct |
17 |
Correct |
126 ms |
17544 KB |
Output is correct |
18 |
Correct |
26 ms |
14584 KB |
Output is correct |
19 |
Correct |
32 ms |
14456 KB |
Output is correct |
20 |
Correct |
79 ms |
16120 KB |
Output is correct |
21 |
Correct |
109 ms |
16240 KB |
Output is correct |
22 |
Correct |
12 ms |
12152 KB |
Output is correct |
23 |
Correct |
26 ms |
14200 KB |
Output is correct |
24 |
Correct |
34 ms |
14172 KB |
Output is correct |
25 |
Correct |
12 ms |
12152 KB |
Output is correct |
26 |
Correct |
13 ms |
12152 KB |
Output is correct |
27 |
Correct |
27 ms |
14632 KB |
Output is correct |
28 |
Correct |
26 ms |
14328 KB |
Output is correct |
29 |
Correct |
23 ms |
14200 KB |
Output is correct |
30 |
Correct |
24 ms |
14200 KB |
Output is correct |
31 |
Correct |
12 ms |
12152 KB |
Output is correct |
32 |
Correct |
13 ms |
12152 KB |
Output is correct |
33 |
Correct |
12 ms |
12152 KB |
Output is correct |
34 |
Correct |
12 ms |
12152 KB |
Output is correct |
35 |
Correct |
12 ms |
12152 KB |
Output is correct |
36 |
Correct |
291 ms |
46120 KB |
Output is correct |
37 |
Correct |
13 ms |
12152 KB |
Output is correct |
38 |
Correct |
303 ms |
45792 KB |
Output is correct |
39 |
Correct |
267 ms |
45032 KB |
Output is correct |
40 |
Correct |
342 ms |
48804 KB |
Output is correct |
41 |
Correct |
334 ms |
50032 KB |
Output is correct |
42 |
Correct |
233 ms |
39288 KB |
Output is correct |
43 |
Correct |
276 ms |
35940 KB |
Output is correct |
44 |
Correct |
312 ms |
35492 KB |
Output is correct |
45 |
Correct |
331 ms |
36168 KB |
Output is correct |
46 |
Correct |
397 ms |
35456 KB |
Output is correct |
47 |
Correct |
267 ms |
39580 KB |
Output is correct |
48 |
Correct |
268 ms |
39416 KB |
Output is correct |
49 |
Correct |
293 ms |
42912 KB |
Output is correct |
50 |
Correct |
292 ms |
43164 KB |
Output is correct |
51 |
Correct |
355 ms |
49360 KB |
Output is correct |
52 |
Correct |
340 ms |
49076 KB |
Output is correct |
53 |
Correct |
268 ms |
35952 KB |
Output is correct |
54 |
Correct |
336 ms |
36228 KB |
Output is correct |
55 |
Correct |
387 ms |
37996 KB |
Output is correct |
56 |
Correct |
481 ms |
37740 KB |
Output is correct |
57 |
Correct |
344 ms |
36116 KB |
Output is correct |
58 |
Correct |
355 ms |
35680 KB |
Output is correct |
59 |
Correct |
309 ms |
35808 KB |
Output is correct |
60 |
Correct |
290 ms |
36256 KB |
Output is correct |
61 |
Correct |
263 ms |
40536 KB |
Output is correct |
62 |
Correct |
241 ms |
40164 KB |
Output is correct |
63 |
Correct |
254 ms |
40548 KB |
Output is correct |
64 |
Correct |
279 ms |
41168 KB |
Output is correct |
65 |
Correct |
482 ms |
38044 KB |
Output is correct |
66 |
Correct |
542 ms |
40292 KB |
Output is correct |
67 |
Correct |
515 ms |
39508 KB |
Output is correct |
68 |
Correct |
281 ms |
35448 KB |
Output is correct |
69 |
Correct |
275 ms |
35576 KB |
Output is correct |
70 |
Correct |
285 ms |
41972 KB |
Output is correct |
71 |
Correct |
290 ms |
42556 KB |
Output is correct |
72 |
Correct |
12 ms |
12152 KB |
Output is correct |
73 |
Correct |
26 ms |
14200 KB |
Output is correct |
74 |
Correct |
26 ms |
14200 KB |
Output is correct |
75 |
Correct |
12 ms |
12152 KB |
Output is correct |
76 |
Correct |
12 ms |
12152 KB |
Output is correct |
77 |
Correct |
26 ms |
14712 KB |
Output is correct |
78 |
Correct |
28 ms |
14456 KB |
Output is correct |
79 |
Correct |
23 ms |
14200 KB |
Output is correct |
80 |
Correct |
26 ms |
14200 KB |
Output is correct |
81 |
Correct |
13 ms |
12152 KB |
Output is correct |
82 |
Correct |
12 ms |
12156 KB |
Output is correct |
83 |
Correct |
12 ms |
12152 KB |
Output is correct |
84 |
Correct |
13 ms |
12152 KB |
Output is correct |
85 |
Correct |
12 ms |
12152 KB |
Output is correct |
86 |
Correct |
110 ms |
17392 KB |
Output is correct |
87 |
Correct |
110 ms |
17400 KB |
Output is correct |
88 |
Correct |
113 ms |
17760 KB |
Output is correct |
89 |
Correct |
26 ms |
14584 KB |
Output is correct |
90 |
Correct |
27 ms |
14328 KB |
Output is correct |
91 |
Correct |
79 ms |
15992 KB |
Output is correct |
92 |
Correct |
92 ms |
16240 KB |
Output is correct |
93 |
Correct |
13 ms |
12152 KB |
Output is correct |
94 |
Correct |
295 ms |
46016 KB |
Output is correct |
95 |
Correct |
327 ms |
45560 KB |
Output is correct |
96 |
Correct |
281 ms |
45048 KB |
Output is correct |
97 |
Correct |
332 ms |
48872 KB |
Output is correct |
98 |
Correct |
295 ms |
49828 KB |
Output is correct |
99 |
Correct |
406 ms |
36772 KB |
Output is correct |
100 |
Correct |
367 ms |
36696 KB |
Output is correct |
101 |
Correct |
469 ms |
37136 KB |
Output is correct |
102 |
Correct |
290 ms |
35940 KB |
Output is correct |
103 |
Correct |
229 ms |
39028 KB |
Output is correct |
104 |
Correct |
253 ms |
40316 KB |
Output is correct |
105 |
Correct |
227 ms |
39288 KB |
Output is correct |
106 |
Correct |
302 ms |
42968 KB |
Output is correct |
107 |
Correct |
289 ms |
42964 KB |
Output is correct |
108 |
Correct |
313 ms |
49324 KB |
Output is correct |
109 |
Correct |
377 ms |
49208 KB |
Output is correct |
110 |
Correct |
306 ms |
35976 KB |
Output is correct |
111 |
Correct |
281 ms |
35956 KB |
Output is correct |
112 |
Correct |
451 ms |
38760 KB |
Output is correct |
113 |
Correct |
404 ms |
38392 KB |
Output is correct |