# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
547328 |
2022-04-10T12:07:41 Z |
Jomnoi |
Railway (BOI17_railway) |
C++17 |
|
170 ms |
28040 KB |
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 1e5 + 10;
int timer, k;
vector <pair <int, int>> graph[MAX_N];
int depth[MAX_N], parent[MAX_N][20];
int st[MAX_N], pos[MAX_N], edge[MAX_N];
int qs[MAX_N];
vector <int> ans;
void dfs(const int &u, const int &p) {
timer++;
st[u] = timer;
pos[timer] = u;
for(int i = 1; i < 20; i++) {
parent[u][i] = parent[parent[u][i - 1]][i - 1];
}
for(auto [v, i] : graph[u]) {
if(v == p) {
continue;
}
edge[v] = i;
depth[v] = depth[u] + 1;
parent[v][0] = u;
dfs(v, u);
}
}
int find_lca(const int &a, const int &b) {
int u = a, v = b;
if(depth[u] < depth[v]) {
swap(u, v);
}
for(int i = 19; i >= 0; i--) {
if(depth[parent[u][i]] >= depth[v]) {
u = parent[u][i];
}
}
for(int i = 19; i >= 0; i--) {
if(parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
return (u == v ? u : parent[u][0]);
}
int dfs2(const int &u, const int &p) {
int sum = qs[u];
for(auto [v, i] : graph[u]) {
if(v != p) {
sum += dfs2(v, u);
}
}
if(sum >= k) {
ans.push_back(edge[u]);
}
return sum;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m >> k;
for(int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
graph[a].emplace_back(b, i);
graph[b].emplace_back(a, i);
}
depth[0] = -1;
dfs(1, -1);
while(m--) {
int s;
cin >> s;
vector <int> vec;
while(s--) {
int x;
cin >> x;
vec.push_back(x);
}
sort(vec.begin(), vec.end(), [&](const int &a, const int &b) {
return st[a] < st[b];
});
stack <int> latest_lca;
stack <int> node;
node.push(vec[0]);
for(int i = 1; i < vec.size(); i++) {
while(!latest_lca.empty() and st[latest_lca.top()] >= st[find_lca(vec[i], node.top())]) {
qs[node.top()]++;
node.pop();
qs[node.top()]++;
node.pop();
qs[latest_lca.top()] -= 2;
node.push(latest_lca.top());
latest_lca.pop();
}
latest_lca.push(find_lca(vec[i], node.top()));
node.push(vec[i]);
}
while(!latest_lca.empty()) {
qs[node.top()]++;
node.pop();
qs[node.top()]++;
node.pop();
qs[latest_lca.top()] -= 2;
node.push(latest_lca.top());
latest_lca.pop();
}
}
dfs2(1, -1);
cout << ans.size() << '\n';
sort(ans.begin(), ans.end());
for(auto v : ans) {
cout << v << ' ';
}
return 0;
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:98:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 1; i < vec.size(); i++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
4052 KB |
Output is correct |
3 |
Correct |
9 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2620 KB |
Output is correct |
6 |
Correct |
8 ms |
4620 KB |
Output is correct |
7 |
Correct |
8 ms |
4224 KB |
Output is correct |
8 |
Correct |
7 ms |
4100 KB |
Output is correct |
9 |
Correct |
6 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
4052 KB |
Output is correct |
3 |
Correct |
9 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2620 KB |
Output is correct |
6 |
Correct |
8 ms |
4620 KB |
Output is correct |
7 |
Correct |
8 ms |
4224 KB |
Output is correct |
8 |
Correct |
7 ms |
4100 KB |
Output is correct |
9 |
Correct |
6 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
70 ms |
4496 KB |
Output is correct |
16 |
Correct |
71 ms |
4492 KB |
Output is correct |
17 |
Correct |
67 ms |
4556 KB |
Output is correct |
18 |
Correct |
7 ms |
4616 KB |
Output is correct |
19 |
Correct |
7 ms |
4224 KB |
Output is correct |
20 |
Correct |
66 ms |
4684 KB |
Output is correct |
21 |
Correct |
64 ms |
4556 KB |
Output is correct |
22 |
Correct |
2 ms |
2680 KB |
Output is correct |
23 |
Correct |
7 ms |
4052 KB |
Output is correct |
24 |
Correct |
8 ms |
4052 KB |
Output is correct |
25 |
Correct |
2 ms |
2676 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
7 ms |
4688 KB |
Output is correct |
28 |
Correct |
8 ms |
4156 KB |
Output is correct |
29 |
Correct |
6 ms |
4096 KB |
Output is correct |
30 |
Correct |
7 ms |
4180 KB |
Output is correct |
31 |
Correct |
3 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2656 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
116 ms |
25852 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
104 ms |
25460 KB |
Output is correct |
4 |
Correct |
154 ms |
24952 KB |
Output is correct |
5 |
Correct |
170 ms |
25844 KB |
Output is correct |
6 |
Correct |
163 ms |
25940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
20552 KB |
Output is correct |
2 |
Correct |
142 ms |
18444 KB |
Output is correct |
3 |
Correct |
109 ms |
17844 KB |
Output is correct |
4 |
Correct |
97 ms |
17952 KB |
Output is correct |
5 |
Correct |
114 ms |
17932 KB |
Output is correct |
6 |
Correct |
130 ms |
22524 KB |
Output is correct |
7 |
Correct |
99 ms |
22396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
20552 KB |
Output is correct |
2 |
Correct |
142 ms |
18444 KB |
Output is correct |
3 |
Correct |
109 ms |
17844 KB |
Output is correct |
4 |
Correct |
97 ms |
17952 KB |
Output is correct |
5 |
Correct |
114 ms |
17932 KB |
Output is correct |
6 |
Correct |
130 ms |
22524 KB |
Output is correct |
7 |
Correct |
99 ms |
22396 KB |
Output is correct |
8 |
Correct |
137 ms |
22648 KB |
Output is correct |
9 |
Correct |
164 ms |
22624 KB |
Output is correct |
10 |
Correct |
165 ms |
27756 KB |
Output is correct |
11 |
Correct |
135 ms |
27636 KB |
Output is correct |
12 |
Correct |
131 ms |
17660 KB |
Output is correct |
13 |
Correct |
129 ms |
17712 KB |
Output is correct |
14 |
Correct |
164 ms |
17880 KB |
Output is correct |
15 |
Correct |
152 ms |
17804 KB |
Output is correct |
16 |
Correct |
121 ms |
17868 KB |
Output is correct |
17 |
Correct |
122 ms |
17956 KB |
Output is correct |
18 |
Correct |
109 ms |
17968 KB |
Output is correct |
19 |
Correct |
99 ms |
18364 KB |
Output is correct |
20 |
Correct |
91 ms |
22764 KB |
Output is correct |
21 |
Correct |
113 ms |
22864 KB |
Output is correct |
22 |
Correct |
104 ms |
22752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
4052 KB |
Output is correct |
3 |
Correct |
9 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2620 KB |
Output is correct |
6 |
Correct |
8 ms |
4620 KB |
Output is correct |
7 |
Correct |
8 ms |
4224 KB |
Output is correct |
8 |
Correct |
7 ms |
4100 KB |
Output is correct |
9 |
Correct |
6 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
70 ms |
4496 KB |
Output is correct |
16 |
Correct |
71 ms |
4492 KB |
Output is correct |
17 |
Correct |
67 ms |
4556 KB |
Output is correct |
18 |
Correct |
7 ms |
4616 KB |
Output is correct |
19 |
Correct |
7 ms |
4224 KB |
Output is correct |
20 |
Correct |
66 ms |
4684 KB |
Output is correct |
21 |
Correct |
64 ms |
4556 KB |
Output is correct |
22 |
Correct |
2 ms |
2680 KB |
Output is correct |
23 |
Correct |
7 ms |
4052 KB |
Output is correct |
24 |
Correct |
8 ms |
4052 KB |
Output is correct |
25 |
Correct |
2 ms |
2676 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
7 ms |
4688 KB |
Output is correct |
28 |
Correct |
8 ms |
4156 KB |
Output is correct |
29 |
Correct |
6 ms |
4096 KB |
Output is correct |
30 |
Correct |
7 ms |
4180 KB |
Output is correct |
31 |
Correct |
3 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2656 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2676 KB |
Output is correct |
36 |
Correct |
116 ms |
25852 KB |
Output is correct |
37 |
Correct |
1 ms |
2644 KB |
Output is correct |
38 |
Correct |
104 ms |
25460 KB |
Output is correct |
39 |
Correct |
154 ms |
24952 KB |
Output is correct |
40 |
Correct |
170 ms |
25844 KB |
Output is correct |
41 |
Correct |
163 ms |
25940 KB |
Output is correct |
42 |
Correct |
89 ms |
20552 KB |
Output is correct |
43 |
Correct |
142 ms |
18444 KB |
Output is correct |
44 |
Correct |
109 ms |
17844 KB |
Output is correct |
45 |
Correct |
97 ms |
17952 KB |
Output is correct |
46 |
Correct |
114 ms |
17932 KB |
Output is correct |
47 |
Correct |
130 ms |
22524 KB |
Output is correct |
48 |
Correct |
99 ms |
22396 KB |
Output is correct |
49 |
Correct |
137 ms |
22648 KB |
Output is correct |
50 |
Correct |
164 ms |
22624 KB |
Output is correct |
51 |
Correct |
165 ms |
27756 KB |
Output is correct |
52 |
Correct |
135 ms |
27636 KB |
Output is correct |
53 |
Correct |
131 ms |
17660 KB |
Output is correct |
54 |
Correct |
129 ms |
17712 KB |
Output is correct |
55 |
Correct |
164 ms |
17880 KB |
Output is correct |
56 |
Correct |
152 ms |
17804 KB |
Output is correct |
57 |
Correct |
121 ms |
17868 KB |
Output is correct |
58 |
Correct |
122 ms |
17956 KB |
Output is correct |
59 |
Correct |
109 ms |
17968 KB |
Output is correct |
60 |
Correct |
99 ms |
18364 KB |
Output is correct |
61 |
Correct |
91 ms |
22764 KB |
Output is correct |
62 |
Correct |
113 ms |
22864 KB |
Output is correct |
63 |
Correct |
104 ms |
22752 KB |
Output is correct |
64 |
Correct |
96 ms |
22784 KB |
Output is correct |
65 |
Correct |
129 ms |
17900 KB |
Output is correct |
66 |
Correct |
163 ms |
17824 KB |
Output is correct |
67 |
Correct |
138 ms |
17800 KB |
Output is correct |
68 |
Correct |
94 ms |
17664 KB |
Output is correct |
69 |
Correct |
99 ms |
17660 KB |
Output is correct |
70 |
Correct |
119 ms |
23288 KB |
Output is correct |
71 |
Correct |
121 ms |
22436 KB |
Output is correct |
72 |
Correct |
2 ms |
2644 KB |
Output is correct |
73 |
Correct |
7 ms |
4164 KB |
Output is correct |
74 |
Correct |
8 ms |
4096 KB |
Output is correct |
75 |
Correct |
2 ms |
2672 KB |
Output is correct |
76 |
Correct |
2 ms |
2676 KB |
Output is correct |
77 |
Correct |
10 ms |
4604 KB |
Output is correct |
78 |
Correct |
9 ms |
4180 KB |
Output is correct |
79 |
Correct |
6 ms |
4096 KB |
Output is correct |
80 |
Correct |
7 ms |
4180 KB |
Output is correct |
81 |
Correct |
2 ms |
2644 KB |
Output is correct |
82 |
Correct |
2 ms |
2644 KB |
Output is correct |
83 |
Correct |
2 ms |
2672 KB |
Output is correct |
84 |
Correct |
2 ms |
2644 KB |
Output is correct |
85 |
Correct |
2 ms |
2680 KB |
Output is correct |
86 |
Correct |
67 ms |
4416 KB |
Output is correct |
87 |
Correct |
70 ms |
4532 KB |
Output is correct |
88 |
Correct |
73 ms |
4532 KB |
Output is correct |
89 |
Correct |
8 ms |
4564 KB |
Output is correct |
90 |
Correct |
8 ms |
4260 KB |
Output is correct |
91 |
Correct |
68 ms |
4580 KB |
Output is correct |
92 |
Correct |
70 ms |
4624 KB |
Output is correct |
93 |
Correct |
2 ms |
2644 KB |
Output is correct |
94 |
Correct |
110 ms |
27676 KB |
Output is correct |
95 |
Correct |
125 ms |
27288 KB |
Output is correct |
96 |
Correct |
143 ms |
26752 KB |
Output is correct |
97 |
Correct |
143 ms |
27628 KB |
Output is correct |
98 |
Correct |
158 ms |
28040 KB |
Output is correct |
99 |
Correct |
118 ms |
17968 KB |
Output is correct |
100 |
Correct |
103 ms |
18020 KB |
Output is correct |
101 |
Correct |
96 ms |
17972 KB |
Output is correct |
102 |
Correct |
110 ms |
18368 KB |
Output is correct |
103 |
Correct |
99 ms |
22476 KB |
Output is correct |
104 |
Correct |
100 ms |
22832 KB |
Output is correct |
105 |
Correct |
90 ms |
22424 KB |
Output is correct |
106 |
Correct |
142 ms |
22884 KB |
Output is correct |
107 |
Correct |
144 ms |
22648 KB |
Output is correct |
108 |
Correct |
153 ms |
27716 KB |
Output is correct |
109 |
Correct |
129 ms |
27728 KB |
Output is correct |
110 |
Correct |
142 ms |
17776 KB |
Output is correct |
111 |
Correct |
132 ms |
17752 KB |
Output is correct |
112 |
Correct |
158 ms |
17792 KB |
Output is correct |
113 |
Correct |
145 ms |
17908 KB |
Output is correct |