# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
915643 |
2024-01-24T12:37:45 Z |
dsyz |
Railway (BOI17_railway) |
C++17 |
|
248 ms |
61008 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,M,K;
vector<pair<ll,ll> > v[MAXN]; //node b, index of edge
vector<ll> ans;
set<pair<ll,ll> > s[MAXN];
ll parent[20][MAXN], depth[MAXN], dist[MAXN];
bool visited[MAXN];
void distdfs(ll x){
visited[x] = 1;
for(auto u : v[x]){
if(visited[u.first] == 0){
dist[u.first] = dist[x] + 1;
visited[u.first] = 1;
distdfs(u.first);
}
}
}
void dfs1(ll x,ll nodeparent,ll nodedepth){
parent[0][x] = nodeparent;
depth[x] = nodedepth;
for(ll i = 0;i < v[x].size();i++){
if(v[x][i].first != nodeparent){
dfs1(v[x][i].first,x,nodedepth + 1);
}
}
}
void lcainit(){
for(ll i = 1;i < 20;i++){
for(ll j = 0;j < N;j++){
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
ll lca(ll u,ll v){
if(depth[u] > depth[v]){
swap(u,v);
}
ll diff = depth[v] - depth[u];
for(ll i = 0;i < 20;i++){
if(diff & (1<<i)){
v = parent[i][v];
}
}
if(u == v){
return u;
}
for(ll i = 19;i >= 0;i--){
if(parent[i][u] != parent[i][v]){
u = parent[i][u];
v = parent[i][v];
}
}
return parent[0][u];
}
void dfs2(ll x,ll p){
ll parentedge = -1;
for(auto u : v[x]){
if(u.first != p){
dfs2(u.first,x);
if(s[u.first].size() > s[x].size()) swap(s[u.first],s[x]); //swap sets is O(1)
//swapping 2 sets, vectors, maps are O(1) so use these data structures
//for pbds, it is a bit different syntax: a.swap(b) is O(1)
s[x].insert(s[u.first].begin(),s[u.first].end());
}else{
parentedge = u.second;
}
}
while(!s[x].empty() && s[x].begin()->first == -1 * depth[x]){
s[x].erase(s[x].begin());
}
if(s[x].size() >= K && parentedge != -1){
ans.push_back(parentedge);
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N>>M>>K;
for(ll i = 0;i < N - 1;i++){
ll a,b;
cin>>a>>b;
a--, b--;
v[a].push_back({b,i});
v[b].push_back({a,i});
}
dist[0] = 0;
visited[0] = 1;
distdfs(0);
dfs1(0,0,0);
lcainit();
for(ll i = 0;i < M;i++){
ll S;
cin>>S;
ll LCA = -1;
ll A[S];
for(ll j = 0;j < S;j++){
cin>>A[j];
A[j]--;
if(j == 0){
LCA = A[j];
}else{
LCA = lca(LCA,A[j]);
}
}
for(ll j = 0;j < S;j++){
s[A[j]].insert({-depth[LCA],i});
}
}
dfs2(0,-1);
sort(ans.begin(),ans.end());
cout<<ans.size()<<'\n';
for(auto u : ans){
cout<<u + 1<<" ";
}
cout<<'\n';
}
Compilation message
railway.cpp: In function 'void dfs1(ll, ll, ll)':
railway.cpp:24:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(ll i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
railway.cpp: In function 'void dfs2(ll, ll)':
railway.cpp:74:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
74 | if(s[x].size() >= K && parentedge != -1){
| ~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
24412 KB |
Output is correct |
2 |
Correct |
10 ms |
25436 KB |
Output is correct |
3 |
Correct |
10 ms |
25352 KB |
Output is correct |
4 |
Correct |
5 ms |
24412 KB |
Output is correct |
5 |
Correct |
5 ms |
24412 KB |
Output is correct |
6 |
Correct |
10 ms |
26172 KB |
Output is correct |
7 |
Correct |
10 ms |
25436 KB |
Output is correct |
8 |
Correct |
9 ms |
25324 KB |
Output is correct |
9 |
Correct |
11 ms |
25692 KB |
Output is correct |
10 |
Correct |
6 ms |
24408 KB |
Output is correct |
11 |
Correct |
6 ms |
24664 KB |
Output is correct |
12 |
Correct |
5 ms |
24412 KB |
Output is correct |
13 |
Correct |
6 ms |
24412 KB |
Output is correct |
14 |
Correct |
6 ms |
24408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
24412 KB |
Output is correct |
2 |
Correct |
10 ms |
25436 KB |
Output is correct |
3 |
Correct |
10 ms |
25352 KB |
Output is correct |
4 |
Correct |
5 ms |
24412 KB |
Output is correct |
5 |
Correct |
5 ms |
24412 KB |
Output is correct |
6 |
Correct |
10 ms |
26172 KB |
Output is correct |
7 |
Correct |
10 ms |
25436 KB |
Output is correct |
8 |
Correct |
9 ms |
25324 KB |
Output is correct |
9 |
Correct |
11 ms |
25692 KB |
Output is correct |
10 |
Correct |
6 ms |
24408 KB |
Output is correct |
11 |
Correct |
6 ms |
24664 KB |
Output is correct |
12 |
Correct |
5 ms |
24412 KB |
Output is correct |
13 |
Correct |
6 ms |
24412 KB |
Output is correct |
14 |
Correct |
6 ms |
24408 KB |
Output is correct |
15 |
Correct |
42 ms |
33040 KB |
Output is correct |
16 |
Correct |
42 ms |
32936 KB |
Output is correct |
17 |
Correct |
48 ms |
33104 KB |
Output is correct |
18 |
Correct |
11 ms |
26200 KB |
Output is correct |
19 |
Correct |
12 ms |
25436 KB |
Output is correct |
20 |
Correct |
42 ms |
32016 KB |
Output is correct |
21 |
Correct |
43 ms |
32056 KB |
Output is correct |
22 |
Correct |
6 ms |
24412 KB |
Output is correct |
23 |
Correct |
14 ms |
25520 KB |
Output is correct |
24 |
Correct |
10 ms |
25436 KB |
Output is correct |
25 |
Correct |
5 ms |
24624 KB |
Output is correct |
26 |
Correct |
7 ms |
24668 KB |
Output is correct |
27 |
Correct |
9 ms |
26204 KB |
Output is correct |
28 |
Correct |
10 ms |
25400 KB |
Output is correct |
29 |
Correct |
8 ms |
25436 KB |
Output is correct |
30 |
Correct |
9 ms |
25436 KB |
Output is correct |
31 |
Correct |
6 ms |
24668 KB |
Output is correct |
32 |
Correct |
5 ms |
24668 KB |
Output is correct |
33 |
Correct |
6 ms |
24880 KB |
Output is correct |
34 |
Correct |
6 ms |
24412 KB |
Output is correct |
35 |
Correct |
6 ms |
24408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
52744 KB |
Output is correct |
2 |
Correct |
6 ms |
24408 KB |
Output is correct |
3 |
Correct |
131 ms |
52240 KB |
Output is correct |
4 |
Correct |
118 ms |
51612 KB |
Output is correct |
5 |
Correct |
128 ms |
51464 KB |
Output is correct |
6 |
Correct |
138 ms |
54808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
47424 KB |
Output is correct |
2 |
Correct |
133 ms |
44460 KB |
Output is correct |
3 |
Correct |
176 ms |
52304 KB |
Output is correct |
4 |
Correct |
163 ms |
52052 KB |
Output is correct |
5 |
Correct |
191 ms |
52428 KB |
Output is correct |
6 |
Correct |
109 ms |
47952 KB |
Output is correct |
7 |
Correct |
107 ms |
47696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
47424 KB |
Output is correct |
2 |
Correct |
133 ms |
44460 KB |
Output is correct |
3 |
Correct |
176 ms |
52304 KB |
Output is correct |
4 |
Correct |
163 ms |
52052 KB |
Output is correct |
5 |
Correct |
191 ms |
52428 KB |
Output is correct |
6 |
Correct |
109 ms |
47952 KB |
Output is correct |
7 |
Correct |
107 ms |
47696 KB |
Output is correct |
8 |
Correct |
123 ms |
46164 KB |
Output is correct |
9 |
Correct |
108 ms |
46160 KB |
Output is correct |
10 |
Correct |
114 ms |
51308 KB |
Output is correct |
11 |
Correct |
108 ms |
51400 KB |
Output is correct |
12 |
Correct |
67 ms |
37068 KB |
Output is correct |
13 |
Correct |
72 ms |
37124 KB |
Output is correct |
14 |
Correct |
128 ms |
45648 KB |
Output is correct |
15 |
Correct |
149 ms |
46028 KB |
Output is correct |
16 |
Correct |
162 ms |
53576 KB |
Output is correct |
17 |
Correct |
156 ms |
54096 KB |
Output is correct |
18 |
Correct |
145 ms |
51140 KB |
Output is correct |
19 |
Correct |
126 ms |
45368 KB |
Output is correct |
20 |
Correct |
108 ms |
48084 KB |
Output is correct |
21 |
Correct |
112 ms |
48284 KB |
Output is correct |
22 |
Correct |
106 ms |
48096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
24412 KB |
Output is correct |
2 |
Correct |
10 ms |
25436 KB |
Output is correct |
3 |
Correct |
10 ms |
25352 KB |
Output is correct |
4 |
Correct |
5 ms |
24412 KB |
Output is correct |
5 |
Correct |
5 ms |
24412 KB |
Output is correct |
6 |
Correct |
10 ms |
26172 KB |
Output is correct |
7 |
Correct |
10 ms |
25436 KB |
Output is correct |
8 |
Correct |
9 ms |
25324 KB |
Output is correct |
9 |
Correct |
11 ms |
25692 KB |
Output is correct |
10 |
Correct |
6 ms |
24408 KB |
Output is correct |
11 |
Correct |
6 ms |
24664 KB |
Output is correct |
12 |
Correct |
5 ms |
24412 KB |
Output is correct |
13 |
Correct |
6 ms |
24412 KB |
Output is correct |
14 |
Correct |
6 ms |
24408 KB |
Output is correct |
15 |
Correct |
42 ms |
33040 KB |
Output is correct |
16 |
Correct |
42 ms |
32936 KB |
Output is correct |
17 |
Correct |
48 ms |
33104 KB |
Output is correct |
18 |
Correct |
11 ms |
26200 KB |
Output is correct |
19 |
Correct |
12 ms |
25436 KB |
Output is correct |
20 |
Correct |
42 ms |
32016 KB |
Output is correct |
21 |
Correct |
43 ms |
32056 KB |
Output is correct |
22 |
Correct |
6 ms |
24412 KB |
Output is correct |
23 |
Correct |
14 ms |
25520 KB |
Output is correct |
24 |
Correct |
10 ms |
25436 KB |
Output is correct |
25 |
Correct |
5 ms |
24624 KB |
Output is correct |
26 |
Correct |
7 ms |
24668 KB |
Output is correct |
27 |
Correct |
9 ms |
26204 KB |
Output is correct |
28 |
Correct |
10 ms |
25400 KB |
Output is correct |
29 |
Correct |
8 ms |
25436 KB |
Output is correct |
30 |
Correct |
9 ms |
25436 KB |
Output is correct |
31 |
Correct |
6 ms |
24668 KB |
Output is correct |
32 |
Correct |
5 ms |
24668 KB |
Output is correct |
33 |
Correct |
6 ms |
24880 KB |
Output is correct |
34 |
Correct |
6 ms |
24412 KB |
Output is correct |
35 |
Correct |
6 ms |
24408 KB |
Output is correct |
36 |
Correct |
153 ms |
52744 KB |
Output is correct |
37 |
Correct |
6 ms |
24408 KB |
Output is correct |
38 |
Correct |
131 ms |
52240 KB |
Output is correct |
39 |
Correct |
118 ms |
51612 KB |
Output is correct |
40 |
Correct |
128 ms |
51464 KB |
Output is correct |
41 |
Correct |
138 ms |
54808 KB |
Output is correct |
42 |
Correct |
115 ms |
47424 KB |
Output is correct |
43 |
Correct |
133 ms |
44460 KB |
Output is correct |
44 |
Correct |
176 ms |
52304 KB |
Output is correct |
45 |
Correct |
163 ms |
52052 KB |
Output is correct |
46 |
Correct |
191 ms |
52428 KB |
Output is correct |
47 |
Correct |
109 ms |
47952 KB |
Output is correct |
48 |
Correct |
107 ms |
47696 KB |
Output is correct |
49 |
Correct |
123 ms |
46164 KB |
Output is correct |
50 |
Correct |
108 ms |
46160 KB |
Output is correct |
51 |
Correct |
114 ms |
51308 KB |
Output is correct |
52 |
Correct |
108 ms |
51400 KB |
Output is correct |
53 |
Correct |
67 ms |
37068 KB |
Output is correct |
54 |
Correct |
72 ms |
37124 KB |
Output is correct |
55 |
Correct |
128 ms |
45648 KB |
Output is correct |
56 |
Correct |
149 ms |
46028 KB |
Output is correct |
57 |
Correct |
162 ms |
53576 KB |
Output is correct |
58 |
Correct |
156 ms |
54096 KB |
Output is correct |
59 |
Correct |
145 ms |
51140 KB |
Output is correct |
60 |
Correct |
126 ms |
45368 KB |
Output is correct |
61 |
Correct |
108 ms |
48084 KB |
Output is correct |
62 |
Correct |
112 ms |
48284 KB |
Output is correct |
63 |
Correct |
106 ms |
48096 KB |
Output is correct |
64 |
Correct |
116 ms |
46252 KB |
Output is correct |
65 |
Correct |
248 ms |
61008 KB |
Output is correct |
66 |
Correct |
197 ms |
55520 KB |
Output is correct |
67 |
Correct |
137 ms |
49744 KB |
Output is correct |
68 |
Correct |
66 ms |
35104 KB |
Output is correct |
69 |
Correct |
58 ms |
35156 KB |
Output is correct |
70 |
Correct |
127 ms |
47532 KB |
Output is correct |
71 |
Correct |
106 ms |
45924 KB |
Output is correct |
72 |
Correct |
6 ms |
24412 KB |
Output is correct |
73 |
Correct |
10 ms |
25436 KB |
Output is correct |
74 |
Correct |
9 ms |
25392 KB |
Output is correct |
75 |
Correct |
6 ms |
24412 KB |
Output is correct |
76 |
Correct |
5 ms |
24412 KB |
Output is correct |
77 |
Correct |
9 ms |
26204 KB |
Output is correct |
78 |
Correct |
9 ms |
25436 KB |
Output is correct |
79 |
Correct |
9 ms |
25436 KB |
Output is correct |
80 |
Correct |
9 ms |
25436 KB |
Output is correct |
81 |
Correct |
5 ms |
24412 KB |
Output is correct |
82 |
Correct |
6 ms |
24412 KB |
Output is correct |
83 |
Correct |
5 ms |
24412 KB |
Output is correct |
84 |
Correct |
6 ms |
24412 KB |
Output is correct |
85 |
Correct |
6 ms |
24412 KB |
Output is correct |
86 |
Correct |
44 ms |
33132 KB |
Output is correct |
87 |
Correct |
38 ms |
33108 KB |
Output is correct |
88 |
Correct |
40 ms |
33048 KB |
Output is correct |
89 |
Correct |
11 ms |
26200 KB |
Output is correct |
90 |
Correct |
9 ms |
25436 KB |
Output is correct |
91 |
Correct |
37 ms |
32216 KB |
Output is correct |
92 |
Correct |
41 ms |
32080 KB |
Output is correct |
93 |
Correct |
5 ms |
24668 KB |
Output is correct |
94 |
Correct |
122 ms |
52660 KB |
Output is correct |
95 |
Correct |
142 ms |
52280 KB |
Output is correct |
96 |
Correct |
114 ms |
51536 KB |
Output is correct |
97 |
Correct |
185 ms |
51620 KB |
Output is correct |
98 |
Correct |
168 ms |
54744 KB |
Output is correct |
99 |
Correct |
195 ms |
57048 KB |
Output is correct |
100 |
Correct |
155 ms |
53328 KB |
Output is correct |
101 |
Correct |
172 ms |
53696 KB |
Output is correct |
102 |
Correct |
125 ms |
44880 KB |
Output is correct |
103 |
Correct |
132 ms |
47848 KB |
Output is correct |
104 |
Correct |
114 ms |
48176 KB |
Output is correct |
105 |
Correct |
121 ms |
47676 KB |
Output is correct |
106 |
Correct |
110 ms |
46284 KB |
Output is correct |
107 |
Correct |
124 ms |
46292 KB |
Output is correct |
108 |
Correct |
101 ms |
51424 KB |
Output is correct |
109 |
Correct |
107 ms |
51440 KB |
Output is correct |
110 |
Correct |
69 ms |
37180 KB |
Output is correct |
111 |
Correct |
77 ms |
37236 KB |
Output is correct |
112 |
Correct |
130 ms |
45520 KB |
Output is correct |
113 |
Correct |
125 ms |
45452 KB |
Output is correct |