#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n,m,k;
int arr[MAXN];
int tmp[MAXN];
bool blocked[MAXN];
int h[MAXN];
vector<int> tosub[MAXN];
int dp[MAXN][32];
set<int> s1[MAXN];
int p[MAXN];
int sz[MAXN];
vector<int> res;
map<pair<int,int>,int> m2;
vector<int> v1[MAXN];
map<int,int> m1;
int side1;
int hold;
void dfs(int curr,int par){
int edgenum = -1;
if(curr!=par){
edgenum = m2[make_pair(curr,par)];
}
int ind = curr;
for(auto x:v1[curr]){
if(x!=par){
dfs(x,curr);
if(s1[p[ind]].size()<s1[p[x]].size()){
ind = p[x];
}
}
}
p[curr] = ind;
for(int x:s1[curr]){
s1[ind].insert(x);
}
for(auto x:v1[curr]){
if(x==par||p[x] == ind){
continue;
}
for(int j:s1[p[x]]){
s1[ind].insert(j);
}
}
for(int x:tosub[curr]){
s1[ind].erase(x);
}
if(s1[ind].size()>=k && edgenum!=-1){
res.push_back(edgenum);
}
}
void precalcdfs(int curr,int par,int depth){
if(curr!=par){
dp[curr][0] = par;
h[curr] = depth;
}else{
h[curr] = 1;
dp[curr][0] = -1;
}
for(int j=1;j<=30;j++){
if(dp[curr][j-1]!=-1){
dp[curr][j] = dp[dp[curr][j-1]][j-1];
}
}
for(int x:v1[curr]){
if(x!=par){
precalcdfs(x,curr,depth+1);
}
}
}
int lca(int x,int y){
if(h[x]>h[y]){
swap(x,y);
}
for(int i=20;i>=0;i--){
if(h[y]-(1<<i) >=h[x]){
y = dp[y][i];
}
}
if(x == y){
return x;
}
for(int i=20;i>=0;i--){
if(dp[x][i]!=-1 && dp[x][i]!=dp[y][i]){
x= dp[x][i];
y = dp[y][i];
}
}
return dp[x][0];
}
int main(){
/*#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif*/
cin>>n>>m>>k;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v1[x].push_back(y);
v1[y].push_back(x);
m2[make_pair(x,y)] = i;
m2[make_pair(y,x)] = i;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
dp[i][j] = -1;
}
}
precalcdfs(1,1,1);
for(int i=1;i<=m;i++){
int len;
cin>>len;
int x;
cin>>x;
len--;
s1[x].insert(i);
int templ = x;
for(int j=1;j<=len;j++){
int x;
cin>>x;
s1[x].insert(i);
templ = lca(templ,x);
}
tosub[templ].push_back(i);
}
dfs(1,1);
sort(res.begin(),res.end());
cout<<res.size()<<endl;
for(int x:res){
cout<<x<<endl;
}
}
Compilation message
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:51:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
51 | if(s1[ind].size()>=k && edgenum!=-1){
| ~~~~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
94328 KB |
Output is correct |
2 |
Correct |
96 ms |
97528 KB |
Output is correct |
3 |
Correct |
82 ms |
97400 KB |
Output is correct |
4 |
Correct |
60 ms |
94328 KB |
Output is correct |
5 |
Correct |
59 ms |
94220 KB |
Output is correct |
6 |
Correct |
98 ms |
98200 KB |
Output is correct |
7 |
Correct |
90 ms |
97528 KB |
Output is correct |
8 |
Correct |
77 ms |
97488 KB |
Output is correct |
9 |
Correct |
80 ms |
97528 KB |
Output is correct |
10 |
Correct |
57 ms |
94328 KB |
Output is correct |
11 |
Correct |
63 ms |
94328 KB |
Output is correct |
12 |
Correct |
59 ms |
94328 KB |
Output is correct |
13 |
Correct |
55 ms |
94328 KB |
Output is correct |
14 |
Correct |
57 ms |
94328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
94328 KB |
Output is correct |
2 |
Correct |
96 ms |
97528 KB |
Output is correct |
3 |
Correct |
82 ms |
97400 KB |
Output is correct |
4 |
Correct |
60 ms |
94328 KB |
Output is correct |
5 |
Correct |
59 ms |
94220 KB |
Output is correct |
6 |
Correct |
98 ms |
98200 KB |
Output is correct |
7 |
Correct |
90 ms |
97528 KB |
Output is correct |
8 |
Correct |
77 ms |
97488 KB |
Output is correct |
9 |
Correct |
80 ms |
97528 KB |
Output is correct |
10 |
Correct |
57 ms |
94328 KB |
Output is correct |
11 |
Correct |
63 ms |
94328 KB |
Output is correct |
12 |
Correct |
59 ms |
94328 KB |
Output is correct |
13 |
Correct |
55 ms |
94328 KB |
Output is correct |
14 |
Correct |
57 ms |
94328 KB |
Output is correct |
15 |
Correct |
169 ms |
103296 KB |
Output is correct |
16 |
Correct |
168 ms |
103288 KB |
Output is correct |
17 |
Correct |
195 ms |
103412 KB |
Output is correct |
18 |
Correct |
92 ms |
98320 KB |
Output is correct |
19 |
Correct |
83 ms |
97528 KB |
Output is correct |
20 |
Correct |
201 ms |
102652 KB |
Output is correct |
21 |
Correct |
191 ms |
102520 KB |
Output is correct |
22 |
Correct |
62 ms |
94328 KB |
Output is correct |
23 |
Correct |
88 ms |
97400 KB |
Output is correct |
24 |
Correct |
87 ms |
97432 KB |
Output is correct |
25 |
Correct |
66 ms |
94264 KB |
Output is correct |
26 |
Correct |
68 ms |
94328 KB |
Output is correct |
27 |
Correct |
109 ms |
98168 KB |
Output is correct |
28 |
Correct |
91 ms |
97528 KB |
Output is correct |
29 |
Correct |
80 ms |
97528 KB |
Output is correct |
30 |
Correct |
87 ms |
97528 KB |
Output is correct |
31 |
Correct |
57 ms |
94328 KB |
Output is correct |
32 |
Correct |
56 ms |
94328 KB |
Output is correct |
33 |
Correct |
56 ms |
94328 KB |
Output is correct |
34 |
Correct |
56 ms |
94328 KB |
Output is correct |
35 |
Correct |
60 ms |
94328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
666 ms |
145448 KB |
Output is correct |
2 |
Correct |
59 ms |
94328 KB |
Output is correct |
3 |
Correct |
605 ms |
146696 KB |
Output is correct |
4 |
Correct |
553 ms |
146168 KB |
Output is correct |
5 |
Correct |
640 ms |
145112 KB |
Output is correct |
6 |
Correct |
672 ms |
147596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
609 ms |
138188 KB |
Output is correct |
2 |
Correct |
643 ms |
135288 KB |
Output is correct |
3 |
Correct |
600 ms |
140532 KB |
Output is correct |
4 |
Correct |
709 ms |
140404 KB |
Output is correct |
5 |
Correct |
623 ms |
141044 KB |
Output is correct |
6 |
Correct |
541 ms |
139992 KB |
Output is correct |
7 |
Correct |
544 ms |
140024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
609 ms |
138188 KB |
Output is correct |
2 |
Correct |
643 ms |
135288 KB |
Output is correct |
3 |
Correct |
600 ms |
140532 KB |
Output is correct |
4 |
Correct |
709 ms |
140404 KB |
Output is correct |
5 |
Correct |
623 ms |
141044 KB |
Output is correct |
6 |
Correct |
541 ms |
139992 KB |
Output is correct |
7 |
Correct |
544 ms |
140024 KB |
Output is correct |
8 |
Correct |
574 ms |
138820 KB |
Output is correct |
9 |
Correct |
566 ms |
138744 KB |
Output is correct |
10 |
Correct |
659 ms |
145008 KB |
Output is correct |
11 |
Correct |
605 ms |
145136 KB |
Output is correct |
12 |
Correct |
414 ms |
130040 KB |
Output is correct |
13 |
Correct |
461 ms |
129912 KB |
Output is correct |
14 |
Correct |
574 ms |
135544 KB |
Output is correct |
15 |
Correct |
573 ms |
135800 KB |
Output is correct |
16 |
Correct |
642 ms |
141812 KB |
Output is correct |
17 |
Correct |
606 ms |
141748 KB |
Output is correct |
18 |
Correct |
608 ms |
140020 KB |
Output is correct |
19 |
Correct |
623 ms |
136312 KB |
Output is correct |
20 |
Correct |
595 ms |
140280 KB |
Output is correct |
21 |
Correct |
592 ms |
140276 KB |
Output is correct |
22 |
Correct |
651 ms |
140408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
94328 KB |
Output is correct |
2 |
Correct |
96 ms |
97528 KB |
Output is correct |
3 |
Correct |
82 ms |
97400 KB |
Output is correct |
4 |
Correct |
60 ms |
94328 KB |
Output is correct |
5 |
Correct |
59 ms |
94220 KB |
Output is correct |
6 |
Correct |
98 ms |
98200 KB |
Output is correct |
7 |
Correct |
90 ms |
97528 KB |
Output is correct |
8 |
Correct |
77 ms |
97488 KB |
Output is correct |
9 |
Correct |
80 ms |
97528 KB |
Output is correct |
10 |
Correct |
57 ms |
94328 KB |
Output is correct |
11 |
Correct |
63 ms |
94328 KB |
Output is correct |
12 |
Correct |
59 ms |
94328 KB |
Output is correct |
13 |
Correct |
55 ms |
94328 KB |
Output is correct |
14 |
Correct |
57 ms |
94328 KB |
Output is correct |
15 |
Correct |
169 ms |
103296 KB |
Output is correct |
16 |
Correct |
168 ms |
103288 KB |
Output is correct |
17 |
Correct |
195 ms |
103412 KB |
Output is correct |
18 |
Correct |
92 ms |
98320 KB |
Output is correct |
19 |
Correct |
83 ms |
97528 KB |
Output is correct |
20 |
Correct |
201 ms |
102652 KB |
Output is correct |
21 |
Correct |
191 ms |
102520 KB |
Output is correct |
22 |
Correct |
62 ms |
94328 KB |
Output is correct |
23 |
Correct |
88 ms |
97400 KB |
Output is correct |
24 |
Correct |
87 ms |
97432 KB |
Output is correct |
25 |
Correct |
66 ms |
94264 KB |
Output is correct |
26 |
Correct |
68 ms |
94328 KB |
Output is correct |
27 |
Correct |
109 ms |
98168 KB |
Output is correct |
28 |
Correct |
91 ms |
97528 KB |
Output is correct |
29 |
Correct |
80 ms |
97528 KB |
Output is correct |
30 |
Correct |
87 ms |
97528 KB |
Output is correct |
31 |
Correct |
57 ms |
94328 KB |
Output is correct |
32 |
Correct |
56 ms |
94328 KB |
Output is correct |
33 |
Correct |
56 ms |
94328 KB |
Output is correct |
34 |
Correct |
56 ms |
94328 KB |
Output is correct |
35 |
Correct |
60 ms |
94328 KB |
Output is correct |
36 |
Correct |
666 ms |
145448 KB |
Output is correct |
37 |
Correct |
59 ms |
94328 KB |
Output is correct |
38 |
Correct |
605 ms |
146696 KB |
Output is correct |
39 |
Correct |
553 ms |
146168 KB |
Output is correct |
40 |
Correct |
640 ms |
145112 KB |
Output is correct |
41 |
Correct |
672 ms |
147596 KB |
Output is correct |
42 |
Correct |
609 ms |
138188 KB |
Output is correct |
43 |
Correct |
643 ms |
135288 KB |
Output is correct |
44 |
Correct |
600 ms |
140532 KB |
Output is correct |
45 |
Correct |
709 ms |
140404 KB |
Output is correct |
46 |
Correct |
623 ms |
141044 KB |
Output is correct |
47 |
Correct |
541 ms |
139992 KB |
Output is correct |
48 |
Correct |
544 ms |
140024 KB |
Output is correct |
49 |
Correct |
574 ms |
138820 KB |
Output is correct |
50 |
Correct |
566 ms |
138744 KB |
Output is correct |
51 |
Correct |
659 ms |
145008 KB |
Output is correct |
52 |
Correct |
605 ms |
145136 KB |
Output is correct |
53 |
Correct |
414 ms |
130040 KB |
Output is correct |
54 |
Correct |
461 ms |
129912 KB |
Output is correct |
55 |
Correct |
574 ms |
135544 KB |
Output is correct |
56 |
Correct |
573 ms |
135800 KB |
Output is correct |
57 |
Correct |
642 ms |
141812 KB |
Output is correct |
58 |
Correct |
606 ms |
141748 KB |
Output is correct |
59 |
Correct |
608 ms |
140020 KB |
Output is correct |
60 |
Correct |
623 ms |
136312 KB |
Output is correct |
61 |
Correct |
595 ms |
140280 KB |
Output is correct |
62 |
Correct |
592 ms |
140276 KB |
Output is correct |
63 |
Correct |
651 ms |
140408 KB |
Output is correct |
64 |
Correct |
664 ms |
139088 KB |
Output is correct |
65 |
Correct |
706 ms |
146936 KB |
Output is correct |
66 |
Correct |
614 ms |
142712 KB |
Output is correct |
67 |
Correct |
597 ms |
138616 KB |
Output is correct |
68 |
Correct |
428 ms |
128248 KB |
Output is correct |
69 |
Correct |
448 ms |
128248 KB |
Output is correct |
70 |
Correct |
742 ms |
140428 KB |
Output is correct |
71 |
Correct |
557 ms |
138652 KB |
Output is correct |
72 |
Correct |
61 ms |
94328 KB |
Output is correct |
73 |
Correct |
87 ms |
97400 KB |
Output is correct |
74 |
Correct |
93 ms |
97392 KB |
Output is correct |
75 |
Correct |
74 ms |
94328 KB |
Output is correct |
76 |
Correct |
60 ms |
94328 KB |
Output is correct |
77 |
Correct |
94 ms |
98168 KB |
Output is correct |
78 |
Correct |
84 ms |
97528 KB |
Output is correct |
79 |
Correct |
79 ms |
97528 KB |
Output is correct |
80 |
Correct |
85 ms |
97616 KB |
Output is correct |
81 |
Correct |
63 ms |
94328 KB |
Output is correct |
82 |
Correct |
65 ms |
94276 KB |
Output is correct |
83 |
Correct |
66 ms |
94328 KB |
Output is correct |
84 |
Correct |
67 ms |
94240 KB |
Output is correct |
85 |
Correct |
63 ms |
94320 KB |
Output is correct |
86 |
Correct |
201 ms |
103420 KB |
Output is correct |
87 |
Correct |
184 ms |
103416 KB |
Output is correct |
88 |
Correct |
179 ms |
103416 KB |
Output is correct |
89 |
Correct |
119 ms |
98296 KB |
Output is correct |
90 |
Correct |
94 ms |
97532 KB |
Output is correct |
91 |
Correct |
190 ms |
102648 KB |
Output is correct |
92 |
Correct |
184 ms |
102520 KB |
Output is correct |
93 |
Correct |
63 ms |
94328 KB |
Output is correct |
94 |
Correct |
726 ms |
146944 KB |
Output is correct |
95 |
Correct |
598 ms |
146720 KB |
Output is correct |
96 |
Correct |
490 ms |
146148 KB |
Output is correct |
97 |
Correct |
646 ms |
145132 KB |
Output is correct |
98 |
Correct |
678 ms |
147544 KB |
Output is correct |
99 |
Correct |
761 ms |
143872 KB |
Output is correct |
100 |
Correct |
796 ms |
141300 KB |
Output is correct |
101 |
Correct |
681 ms |
141800 KB |
Output is correct |
102 |
Correct |
690 ms |
135416 KB |
Output is correct |
103 |
Correct |
620 ms |
139896 KB |
Output is correct |
104 |
Correct |
585 ms |
140384 KB |
Output is correct |
105 |
Correct |
620 ms |
139840 KB |
Output is correct |
106 |
Correct |
602 ms |
138880 KB |
Output is correct |
107 |
Correct |
540 ms |
138616 KB |
Output is correct |
108 |
Correct |
619 ms |
144880 KB |
Output is correct |
109 |
Correct |
610 ms |
144920 KB |
Output is correct |
110 |
Correct |
410 ms |
129912 KB |
Output is correct |
111 |
Correct |
402 ms |
129784 KB |
Output is correct |
112 |
Correct |
584 ms |
135544 KB |
Output is correct |
113 |
Correct |
592 ms |
135672 KB |
Output is correct |