# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
462613 |
2021-08-11T00:12:16 Z |
JovanB |
Railway (BOI17_railway) |
C++17 |
|
155 ms |
26928 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXLOG = 18;
int par[100005][MAXLOG+1];
vector <pair <int, int>> graf[100005];
int depth[100005];
int in[100005];
int out[100005];
int x[100005];
int pre[100005];
vector <int> res;
int tajm;
void dfs_pre(int v, int parent){
depth[v] = depth[parent] + 1;
par[v][0] = parent;
for(int j=1; j<MAXLOG; j++){
par[v][j] = par[par[v][j-1]][j-1];
}
in[v] = ++tajm;
for(auto d : graf[v]){
int c = d.first;
if(c != parent) dfs_pre(c, v);
}
out[v] = tajm;
}
bool is_parent(int a, int b){
return in[a] <= in[b] && out[b] <= out[a];
}
bool cmp(int a, int b){
return in[a] < in[b];
}
int k;
int lca(int a, int b){
if(is_parent(a, b)) return a;
if(is_parent(b, a)) return b;
for(int j=MAXLOG-1; j>=0; j--){
if(!is_parent(par[a][j], b)) a = par[a][j];
}
return par[a][0];
}
int dfs(int v){
int tren = 0;
int koji = 0;
for(auto c : graf[v]){
if(c.first != par[v][0]) tren += dfs(c.first);
else koji = c.second;
}
tren += pre[v];
if(tren >= k) res.push_back(koji);
return tren;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
out[0] = 2e5;
int n, m;
cin >> n >> m >> k;
for(int i=1; i<n; i++){
int a, b;
cin >> a >> b;
graf[a].push_back({b, i});
graf[b].push_back({a, i});
}
dfs_pre(1, 0);
for(int i=1; i<=m; i++){
int len;
cin >> len;
for(int j=1; j<=len; j++){
cin >> x[j];
}
sort(x+1, x+1+len, cmp);
int mn = n+5;
int v = x[len];
int kolko = 0;
vector <int> sad;
for(int j=len; j>=1; j--){
v = lca(v, x[j]);
if(out[x[j]] < mn){
pre[x[j]]++;
kolko++;
mn = out[x[j]];
sad.push_back(x[j]);
}
}
for(int j=0; j<sad.size()-1; j++){
pre[lca(sad[j], sad[j+1])]--;
}
pre[v]--;
}
dfs(1);
sort(res.begin(), res.end());
cout << res.size() << "\n";
for(auto c : res) cout << c << " ";
return 0;
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j=0; j<sad.size()-1; j++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4028 KB |
Output is correct |
3 |
Correct |
9 ms |
4044 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
4556 KB |
Output is correct |
7 |
Correct |
8 ms |
4100 KB |
Output is correct |
8 |
Correct |
8 ms |
4068 KB |
Output is correct |
9 |
Correct |
7 ms |
4044 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2684 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4028 KB |
Output is correct |
3 |
Correct |
9 ms |
4044 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
4556 KB |
Output is correct |
7 |
Correct |
8 ms |
4100 KB |
Output is correct |
8 |
Correct |
8 ms |
4068 KB |
Output is correct |
9 |
Correct |
7 ms |
4044 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2684 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
28 ms |
4360 KB |
Output is correct |
16 |
Correct |
29 ms |
4412 KB |
Output is correct |
17 |
Correct |
30 ms |
4428 KB |
Output is correct |
18 |
Correct |
9 ms |
4508 KB |
Output is correct |
19 |
Correct |
8 ms |
4152 KB |
Output is correct |
20 |
Correct |
41 ms |
4620 KB |
Output is correct |
21 |
Correct |
63 ms |
4536 KB |
Output is correct |
22 |
Correct |
3 ms |
2636 KB |
Output is correct |
23 |
Correct |
8 ms |
4064 KB |
Output is correct |
24 |
Correct |
8 ms |
4044 KB |
Output is correct |
25 |
Correct |
2 ms |
2636 KB |
Output is correct |
26 |
Correct |
2 ms |
2688 KB |
Output is correct |
27 |
Correct |
10 ms |
4556 KB |
Output is correct |
28 |
Correct |
9 ms |
4224 KB |
Output is correct |
29 |
Correct |
7 ms |
4052 KB |
Output is correct |
30 |
Correct |
7 ms |
3996 KB |
Output is correct |
31 |
Correct |
3 ms |
2636 KB |
Output is correct |
32 |
Correct |
3 ms |
2664 KB |
Output is correct |
33 |
Correct |
3 ms |
2636 KB |
Output is correct |
34 |
Correct |
2 ms |
2684 KB |
Output is correct |
35 |
Correct |
3 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
26848 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
92 ms |
26552 KB |
Output is correct |
4 |
Correct |
73 ms |
25952 KB |
Output is correct |
5 |
Correct |
80 ms |
26684 KB |
Output is correct |
6 |
Correct |
85 ms |
26928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
21480 KB |
Output is correct |
2 |
Correct |
110 ms |
17656 KB |
Output is correct |
3 |
Correct |
138 ms |
17168 KB |
Output is correct |
4 |
Correct |
123 ms |
17164 KB |
Output is correct |
5 |
Correct |
127 ms |
17184 KB |
Output is correct |
6 |
Correct |
98 ms |
21708 KB |
Output is correct |
7 |
Correct |
98 ms |
21672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
21480 KB |
Output is correct |
2 |
Correct |
110 ms |
17656 KB |
Output is correct |
3 |
Correct |
138 ms |
17168 KB |
Output is correct |
4 |
Correct |
123 ms |
17164 KB |
Output is correct |
5 |
Correct |
127 ms |
17184 KB |
Output is correct |
6 |
Correct |
98 ms |
21708 KB |
Output is correct |
7 |
Correct |
98 ms |
21672 KB |
Output is correct |
8 |
Correct |
115 ms |
21848 KB |
Output is correct |
9 |
Correct |
108 ms |
21900 KB |
Output is correct |
10 |
Correct |
95 ms |
26560 KB |
Output is correct |
11 |
Correct |
87 ms |
26500 KB |
Output is correct |
12 |
Correct |
89 ms |
17076 KB |
Output is correct |
13 |
Correct |
93 ms |
16884 KB |
Output is correct |
14 |
Correct |
129 ms |
17096 KB |
Output is correct |
15 |
Correct |
118 ms |
17092 KB |
Output is correct |
16 |
Correct |
144 ms |
17180 KB |
Output is correct |
17 |
Correct |
131 ms |
17188 KB |
Output is correct |
18 |
Correct |
153 ms |
17168 KB |
Output is correct |
19 |
Correct |
155 ms |
17604 KB |
Output is correct |
20 |
Correct |
114 ms |
22140 KB |
Output is correct |
21 |
Correct |
123 ms |
22040 KB |
Output is correct |
22 |
Correct |
132 ms |
21912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4028 KB |
Output is correct |
3 |
Correct |
9 ms |
4044 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
4556 KB |
Output is correct |
7 |
Correct |
8 ms |
4100 KB |
Output is correct |
8 |
Correct |
8 ms |
4068 KB |
Output is correct |
9 |
Correct |
7 ms |
4044 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2684 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
28 ms |
4360 KB |
Output is correct |
16 |
Correct |
29 ms |
4412 KB |
Output is correct |
17 |
Correct |
30 ms |
4428 KB |
Output is correct |
18 |
Correct |
9 ms |
4508 KB |
Output is correct |
19 |
Correct |
8 ms |
4152 KB |
Output is correct |
20 |
Correct |
41 ms |
4620 KB |
Output is correct |
21 |
Correct |
63 ms |
4536 KB |
Output is correct |
22 |
Correct |
3 ms |
2636 KB |
Output is correct |
23 |
Correct |
8 ms |
4064 KB |
Output is correct |
24 |
Correct |
8 ms |
4044 KB |
Output is correct |
25 |
Correct |
2 ms |
2636 KB |
Output is correct |
26 |
Correct |
2 ms |
2688 KB |
Output is correct |
27 |
Correct |
10 ms |
4556 KB |
Output is correct |
28 |
Correct |
9 ms |
4224 KB |
Output is correct |
29 |
Correct |
7 ms |
4052 KB |
Output is correct |
30 |
Correct |
7 ms |
3996 KB |
Output is correct |
31 |
Correct |
3 ms |
2636 KB |
Output is correct |
32 |
Correct |
3 ms |
2664 KB |
Output is correct |
33 |
Correct |
3 ms |
2636 KB |
Output is correct |
34 |
Correct |
2 ms |
2684 KB |
Output is correct |
35 |
Correct |
3 ms |
2636 KB |
Output is correct |
36 |
Correct |
113 ms |
26848 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
92 ms |
26552 KB |
Output is correct |
39 |
Correct |
73 ms |
25952 KB |
Output is correct |
40 |
Correct |
80 ms |
26684 KB |
Output is correct |
41 |
Correct |
85 ms |
26928 KB |
Output is correct |
42 |
Correct |
89 ms |
21480 KB |
Output is correct |
43 |
Correct |
110 ms |
17656 KB |
Output is correct |
44 |
Correct |
138 ms |
17168 KB |
Output is correct |
45 |
Correct |
123 ms |
17164 KB |
Output is correct |
46 |
Correct |
127 ms |
17184 KB |
Output is correct |
47 |
Correct |
98 ms |
21708 KB |
Output is correct |
48 |
Correct |
98 ms |
21672 KB |
Output is correct |
49 |
Correct |
115 ms |
21848 KB |
Output is correct |
50 |
Correct |
108 ms |
21900 KB |
Output is correct |
51 |
Correct |
95 ms |
26560 KB |
Output is correct |
52 |
Correct |
87 ms |
26500 KB |
Output is correct |
53 |
Correct |
89 ms |
17076 KB |
Output is correct |
54 |
Correct |
93 ms |
16884 KB |
Output is correct |
55 |
Correct |
129 ms |
17096 KB |
Output is correct |
56 |
Correct |
118 ms |
17092 KB |
Output is correct |
57 |
Correct |
144 ms |
17180 KB |
Output is correct |
58 |
Correct |
131 ms |
17188 KB |
Output is correct |
59 |
Correct |
153 ms |
17168 KB |
Output is correct |
60 |
Correct |
155 ms |
17604 KB |
Output is correct |
61 |
Correct |
114 ms |
22140 KB |
Output is correct |
62 |
Correct |
123 ms |
22040 KB |
Output is correct |
63 |
Correct |
132 ms |
21912 KB |
Output is correct |
64 |
Correct |
93 ms |
21992 KB |
Output is correct |
65 |
Correct |
132 ms |
17156 KB |
Output is correct |
66 |
Correct |
127 ms |
17036 KB |
Output is correct |
67 |
Correct |
138 ms |
17092 KB |
Output is correct |
68 |
Correct |
78 ms |
16864 KB |
Output is correct |
69 |
Correct |
91 ms |
16876 KB |
Output is correct |
70 |
Correct |
102 ms |
22404 KB |
Output is correct |
71 |
Correct |
106 ms |
21724 KB |
Output is correct |
72 |
Correct |
2 ms |
2656 KB |
Output is correct |
73 |
Correct |
7 ms |
4044 KB |
Output is correct |
74 |
Correct |
7 ms |
3976 KB |
Output is correct |
75 |
Correct |
2 ms |
2656 KB |
Output is correct |
76 |
Correct |
2 ms |
2636 KB |
Output is correct |
77 |
Correct |
8 ms |
4556 KB |
Output is correct |
78 |
Correct |
10 ms |
4172 KB |
Output is correct |
79 |
Correct |
7 ms |
3956 KB |
Output is correct |
80 |
Correct |
7 ms |
4104 KB |
Output is correct |
81 |
Correct |
2 ms |
2636 KB |
Output is correct |
82 |
Correct |
2 ms |
2656 KB |
Output is correct |
83 |
Correct |
2 ms |
2636 KB |
Output is correct |
84 |
Correct |
2 ms |
2636 KB |
Output is correct |
85 |
Correct |
2 ms |
2688 KB |
Output is correct |
86 |
Correct |
33 ms |
4428 KB |
Output is correct |
87 |
Correct |
34 ms |
4460 KB |
Output is correct |
88 |
Correct |
29 ms |
4412 KB |
Output is correct |
89 |
Correct |
8 ms |
4524 KB |
Output is correct |
90 |
Correct |
7 ms |
4080 KB |
Output is correct |
91 |
Correct |
43 ms |
4552 KB |
Output is correct |
92 |
Correct |
43 ms |
4544 KB |
Output is correct |
93 |
Correct |
2 ms |
2636 KB |
Output is correct |
94 |
Correct |
105 ms |
26796 KB |
Output is correct |
95 |
Correct |
80 ms |
26568 KB |
Output is correct |
96 |
Correct |
84 ms |
25988 KB |
Output is correct |
97 |
Correct |
105 ms |
26728 KB |
Output is correct |
98 |
Correct |
87 ms |
26860 KB |
Output is correct |
99 |
Correct |
133 ms |
17184 KB |
Output is correct |
100 |
Correct |
151 ms |
17208 KB |
Output is correct |
101 |
Correct |
144 ms |
17092 KB |
Output is correct |
102 |
Correct |
138 ms |
17576 KB |
Output is correct |
103 |
Correct |
111 ms |
21692 KB |
Output is correct |
104 |
Correct |
101 ms |
22016 KB |
Output is correct |
105 |
Correct |
106 ms |
21652 KB |
Output is correct |
106 |
Correct |
120 ms |
22040 KB |
Output is correct |
107 |
Correct |
121 ms |
21808 KB |
Output is correct |
108 |
Correct |
81 ms |
26620 KB |
Output is correct |
109 |
Correct |
81 ms |
26552 KB |
Output is correct |
110 |
Correct |
110 ms |
16880 KB |
Output is correct |
111 |
Correct |
95 ms |
16904 KB |
Output is correct |
112 |
Correct |
146 ms |
17036 KB |
Output is correct |
113 |
Correct |
125 ms |
17104 KB |
Output is correct |