#include <bits/stdc++.h>
using namespace std;
// #undef _GLIBCXX_DEBUG // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe") // byte swap
// #pragma GCC target("aes,pclmul,rdrnd") // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<n;i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;
vvi adj(100001);
vl d(100001);
vpl order;
void dfs(int pos, int last = -1, int depth = 0){
d[pos] = depth;
for(auto u : adj[pos]){
if(u == last) continue;
dfs(u, pos, depth+1);
}
order.pb({depth, pos});
}
int main() {
// cout << fixed << setprecision(20);
// auto start = std::chrono::steady_clock::now(); // since(start).count()
cin.tie(0)->sync_with_stdio(0);
int n, m, k, a, val, from, to;
cin >> n >> m >> k;
map<pl, ll> toRoad;
fo(i, n-1){
cin >> from >> to;
adj[--from].pb(--to);
adj[to].pb(from);
toRoad[{from, to}] = i+1;
toRoad[{to, from}] = i+1;
}
dfs(0);
vvl bl(24, vl(100001, 0));
fo(i, adj.size()){
for(auto v : adj[i]){
if(d[v] >= d[i]) continue;
bl[0][i] = v;
}
}
fo(i, 22){
fo(j, n){
bl[i+1][j] = bl[i][bl[i][j]];
}
}
vvl root(100001);
vector<set<ll>> wantRoad(100001);
fo(x, m){
cin >> a;
vl v;
fo(y, a){
cin >> val;
val--;
v.pb(val);
wantRoad[val].insert(x);
}
ll deapest = v[0];
fo(i, a){
if(!i) continue;
ll current = v[i];
if(d[current]<d[deapest]) swap(deapest, current);
for(int m = d[current]-d[deapest];m;m-=LSOne(m)){
current = bl[__builtin_ctz(LSOne(m))][current];
}
if(current == deapest) continue;
for(int j = 22; j>=0;j--){
if(bl[j][current] == bl[j][deapest]) continue;
current = bl[j][current];
deapest = bl[j][deapest];
}
current = bl[0][current];
deapest = bl[0][deapest];
}
root[deapest].pb(x);
}
vl ans;
sort(rall(order));
for(auto ver : order){
if(!ver.S) continue;
for(auto toRem : root[ver.S]){
wantRoad[ver.S].erase(toRem);
}
if(wantRoad[ver.S].size() >= k) ans.pb(toRoad[{ver.S, bl[0][ver.S]}]);
if(wantRoad[ver.S].size() > wantRoad[bl[0][ver.S]].size()) swap(wantRoad[ver.S], wantRoad[bl[0][ver.S]]);
for(auto ve : wantRoad[ver.S]){
wantRoad[bl[0][ver.S]].insert(ve);
}
}
sort(all(ans));
cout << ans.size() << "\n";
fo(i, ans.size()){
cout << ans[i] << " ";
}
return 0;
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:20:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define fo(i, n) for(int i=0;i<n;i++)
......
78 | fo(i, adj.size()){
| ~~~~~~~~~~~~~
railway.cpp:78:5: note: in expansion of macro 'fo'
78 | fo(i, adj.size()){
| ^~
railway.cpp:131:35: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
131 | if(wantRoad[ver.S].size() >= k) ans.pb(toRoad[{ver.S, bl[0][ver.S]}]);
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~
railway.cpp:20:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define fo(i, n) for(int i=0;i<n;i++)
......
139 | fo(i, ans.size()){
| ~~~~~~~~~~~~~
railway.cpp:139:5: note: in expansion of macro 'fo'
139 | fo(i, ans.size()){
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
29304 KB |
Output is correct |
2 |
Correct |
20 ms |
31316 KB |
Output is correct |
3 |
Correct |
23 ms |
31304 KB |
Output is correct |
4 |
Correct |
12 ms |
29252 KB |
Output is correct |
5 |
Correct |
12 ms |
29252 KB |
Output is correct |
6 |
Correct |
20 ms |
31924 KB |
Output is correct |
7 |
Correct |
19 ms |
31356 KB |
Output is correct |
8 |
Correct |
19 ms |
31428 KB |
Output is correct |
9 |
Correct |
20 ms |
31496 KB |
Output is correct |
10 |
Correct |
12 ms |
29252 KB |
Output is correct |
11 |
Correct |
14 ms |
29344 KB |
Output is correct |
12 |
Correct |
12 ms |
29360 KB |
Output is correct |
13 |
Correct |
13 ms |
29380 KB |
Output is correct |
14 |
Correct |
12 ms |
29284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
29304 KB |
Output is correct |
2 |
Correct |
20 ms |
31316 KB |
Output is correct |
3 |
Correct |
23 ms |
31304 KB |
Output is correct |
4 |
Correct |
12 ms |
29252 KB |
Output is correct |
5 |
Correct |
12 ms |
29252 KB |
Output is correct |
6 |
Correct |
20 ms |
31924 KB |
Output is correct |
7 |
Correct |
19 ms |
31356 KB |
Output is correct |
8 |
Correct |
19 ms |
31428 KB |
Output is correct |
9 |
Correct |
20 ms |
31496 KB |
Output is correct |
10 |
Correct |
12 ms |
29252 KB |
Output is correct |
11 |
Correct |
14 ms |
29344 KB |
Output is correct |
12 |
Correct |
12 ms |
29360 KB |
Output is correct |
13 |
Correct |
13 ms |
29380 KB |
Output is correct |
14 |
Correct |
12 ms |
29284 KB |
Output is correct |
15 |
Correct |
49 ms |
37632 KB |
Output is correct |
16 |
Correct |
49 ms |
37612 KB |
Output is correct |
17 |
Correct |
50 ms |
37796 KB |
Output is correct |
18 |
Correct |
23 ms |
32072 KB |
Output is correct |
19 |
Correct |
27 ms |
31424 KB |
Output is correct |
20 |
Correct |
47 ms |
36476 KB |
Output is correct |
21 |
Correct |
44 ms |
36428 KB |
Output is correct |
22 |
Correct |
13 ms |
29332 KB |
Output is correct |
23 |
Correct |
22 ms |
31304 KB |
Output is correct |
24 |
Correct |
20 ms |
31304 KB |
Output is correct |
25 |
Correct |
12 ms |
29252 KB |
Output is correct |
26 |
Correct |
13 ms |
29252 KB |
Output is correct |
27 |
Correct |
20 ms |
31888 KB |
Output is correct |
28 |
Correct |
20 ms |
31360 KB |
Output is correct |
29 |
Correct |
19 ms |
31372 KB |
Output is correct |
30 |
Correct |
21 ms |
31484 KB |
Output is correct |
31 |
Correct |
12 ms |
29344 KB |
Output is correct |
32 |
Correct |
13 ms |
29300 KB |
Output is correct |
33 |
Correct |
12 ms |
29252 KB |
Output is correct |
34 |
Correct |
12 ms |
29308 KB |
Output is correct |
35 |
Correct |
12 ms |
29252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
208 ms |
68212 KB |
Output is correct |
2 |
Correct |
13 ms |
29304 KB |
Output is correct |
3 |
Correct |
171 ms |
67324 KB |
Output is correct |
4 |
Correct |
158 ms |
66244 KB |
Output is correct |
5 |
Correct |
186 ms |
66392 KB |
Output is correct |
6 |
Correct |
162 ms |
68828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
62272 KB |
Output is correct |
2 |
Correct |
202 ms |
61064 KB |
Output is correct |
3 |
Correct |
232 ms |
66180 KB |
Output is correct |
4 |
Correct |
228 ms |
66500 KB |
Output is correct |
5 |
Correct |
236 ms |
67676 KB |
Output is correct |
6 |
Correct |
173 ms |
62732 KB |
Output is correct |
7 |
Correct |
158 ms |
62524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
62272 KB |
Output is correct |
2 |
Correct |
202 ms |
61064 KB |
Output is correct |
3 |
Correct |
232 ms |
66180 KB |
Output is correct |
4 |
Correct |
228 ms |
66500 KB |
Output is correct |
5 |
Correct |
236 ms |
67676 KB |
Output is correct |
6 |
Correct |
173 ms |
62732 KB |
Output is correct |
7 |
Correct |
158 ms |
62524 KB |
Output is correct |
8 |
Correct |
212 ms |
61036 KB |
Output is correct |
9 |
Correct |
168 ms |
60932 KB |
Output is correct |
10 |
Correct |
140 ms |
66288 KB |
Output is correct |
11 |
Correct |
137 ms |
66188 KB |
Output is correct |
12 |
Correct |
150 ms |
53080 KB |
Output is correct |
13 |
Correct |
112 ms |
53084 KB |
Output is correct |
14 |
Correct |
209 ms |
59756 KB |
Output is correct |
15 |
Correct |
191 ms |
59968 KB |
Output is correct |
16 |
Correct |
256 ms |
67560 KB |
Output is correct |
17 |
Correct |
227 ms |
67264 KB |
Output is correct |
18 |
Correct |
217 ms |
65796 KB |
Output is correct |
19 |
Correct |
217 ms |
62900 KB |
Output is correct |
20 |
Correct |
167 ms |
63124 KB |
Output is correct |
21 |
Correct |
167 ms |
63420 KB |
Output is correct |
22 |
Correct |
166 ms |
63036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
29304 KB |
Output is correct |
2 |
Correct |
20 ms |
31316 KB |
Output is correct |
3 |
Correct |
23 ms |
31304 KB |
Output is correct |
4 |
Correct |
12 ms |
29252 KB |
Output is correct |
5 |
Correct |
12 ms |
29252 KB |
Output is correct |
6 |
Correct |
20 ms |
31924 KB |
Output is correct |
7 |
Correct |
19 ms |
31356 KB |
Output is correct |
8 |
Correct |
19 ms |
31428 KB |
Output is correct |
9 |
Correct |
20 ms |
31496 KB |
Output is correct |
10 |
Correct |
12 ms |
29252 KB |
Output is correct |
11 |
Correct |
14 ms |
29344 KB |
Output is correct |
12 |
Correct |
12 ms |
29360 KB |
Output is correct |
13 |
Correct |
13 ms |
29380 KB |
Output is correct |
14 |
Correct |
12 ms |
29284 KB |
Output is correct |
15 |
Correct |
49 ms |
37632 KB |
Output is correct |
16 |
Correct |
49 ms |
37612 KB |
Output is correct |
17 |
Correct |
50 ms |
37796 KB |
Output is correct |
18 |
Correct |
23 ms |
32072 KB |
Output is correct |
19 |
Correct |
27 ms |
31424 KB |
Output is correct |
20 |
Correct |
47 ms |
36476 KB |
Output is correct |
21 |
Correct |
44 ms |
36428 KB |
Output is correct |
22 |
Correct |
13 ms |
29332 KB |
Output is correct |
23 |
Correct |
22 ms |
31304 KB |
Output is correct |
24 |
Correct |
20 ms |
31304 KB |
Output is correct |
25 |
Correct |
12 ms |
29252 KB |
Output is correct |
26 |
Correct |
13 ms |
29252 KB |
Output is correct |
27 |
Correct |
20 ms |
31888 KB |
Output is correct |
28 |
Correct |
20 ms |
31360 KB |
Output is correct |
29 |
Correct |
19 ms |
31372 KB |
Output is correct |
30 |
Correct |
21 ms |
31484 KB |
Output is correct |
31 |
Correct |
12 ms |
29344 KB |
Output is correct |
32 |
Correct |
13 ms |
29300 KB |
Output is correct |
33 |
Correct |
12 ms |
29252 KB |
Output is correct |
34 |
Correct |
12 ms |
29308 KB |
Output is correct |
35 |
Correct |
12 ms |
29252 KB |
Output is correct |
36 |
Correct |
208 ms |
68212 KB |
Output is correct |
37 |
Correct |
13 ms |
29304 KB |
Output is correct |
38 |
Correct |
171 ms |
67324 KB |
Output is correct |
39 |
Correct |
158 ms |
66244 KB |
Output is correct |
40 |
Correct |
186 ms |
66392 KB |
Output is correct |
41 |
Correct |
162 ms |
68828 KB |
Output is correct |
42 |
Correct |
166 ms |
62272 KB |
Output is correct |
43 |
Correct |
202 ms |
61064 KB |
Output is correct |
44 |
Correct |
232 ms |
66180 KB |
Output is correct |
45 |
Correct |
228 ms |
66500 KB |
Output is correct |
46 |
Correct |
236 ms |
67676 KB |
Output is correct |
47 |
Correct |
173 ms |
62732 KB |
Output is correct |
48 |
Correct |
158 ms |
62524 KB |
Output is correct |
49 |
Correct |
212 ms |
61036 KB |
Output is correct |
50 |
Correct |
168 ms |
60932 KB |
Output is correct |
51 |
Correct |
140 ms |
66288 KB |
Output is correct |
52 |
Correct |
137 ms |
66188 KB |
Output is correct |
53 |
Correct |
150 ms |
53080 KB |
Output is correct |
54 |
Correct |
112 ms |
53084 KB |
Output is correct |
55 |
Correct |
209 ms |
59756 KB |
Output is correct |
56 |
Correct |
191 ms |
59968 KB |
Output is correct |
57 |
Correct |
256 ms |
67560 KB |
Output is correct |
58 |
Correct |
227 ms |
67264 KB |
Output is correct |
59 |
Correct |
217 ms |
65796 KB |
Output is correct |
60 |
Correct |
217 ms |
62900 KB |
Output is correct |
61 |
Correct |
167 ms |
63124 KB |
Output is correct |
62 |
Correct |
167 ms |
63420 KB |
Output is correct |
63 |
Correct |
166 ms |
63036 KB |
Output is correct |
64 |
Correct |
162 ms |
61788 KB |
Output is correct |
65 |
Correct |
260 ms |
75304 KB |
Output is correct |
66 |
Correct |
218 ms |
69812 KB |
Output is correct |
67 |
Correct |
207 ms |
64832 KB |
Output is correct |
68 |
Correct |
116 ms |
51652 KB |
Output is correct |
69 |
Correct |
112 ms |
51724 KB |
Output is correct |
70 |
Correct |
184 ms |
63388 KB |
Output is correct |
71 |
Correct |
157 ms |
61004 KB |
Output is correct |
72 |
Correct |
11 ms |
29320 KB |
Output is correct |
73 |
Correct |
20 ms |
31304 KB |
Output is correct |
74 |
Correct |
24 ms |
31324 KB |
Output is correct |
75 |
Correct |
11 ms |
29304 KB |
Output is correct |
76 |
Correct |
11 ms |
29252 KB |
Output is correct |
77 |
Correct |
20 ms |
31956 KB |
Output is correct |
78 |
Correct |
19 ms |
31368 KB |
Output is correct |
79 |
Correct |
17 ms |
31460 KB |
Output is correct |
80 |
Correct |
19 ms |
31452 KB |
Output is correct |
81 |
Correct |
11 ms |
29252 KB |
Output is correct |
82 |
Correct |
12 ms |
29252 KB |
Output is correct |
83 |
Correct |
12 ms |
29252 KB |
Output is correct |
84 |
Correct |
12 ms |
29348 KB |
Output is correct |
85 |
Correct |
12 ms |
29308 KB |
Output is correct |
86 |
Correct |
47 ms |
37668 KB |
Output is correct |
87 |
Correct |
47 ms |
37628 KB |
Output is correct |
88 |
Correct |
48 ms |
37828 KB |
Output is correct |
89 |
Correct |
21 ms |
32012 KB |
Output is correct |
90 |
Correct |
20 ms |
31420 KB |
Output is correct |
91 |
Correct |
47 ms |
36500 KB |
Output is correct |
92 |
Correct |
43 ms |
36412 KB |
Output is correct |
93 |
Correct |
12 ms |
29364 KB |
Output is correct |
94 |
Correct |
187 ms |
68084 KB |
Output is correct |
95 |
Correct |
173 ms |
67260 KB |
Output is correct |
96 |
Correct |
162 ms |
66324 KB |
Output is correct |
97 |
Correct |
163 ms |
66320 KB |
Output is correct |
98 |
Correct |
154 ms |
68908 KB |
Output is correct |
99 |
Correct |
233 ms |
70080 KB |
Output is correct |
100 |
Correct |
233 ms |
66668 KB |
Output is correct |
101 |
Correct |
233 ms |
67620 KB |
Output is correct |
102 |
Correct |
201 ms |
61008 KB |
Output is correct |
103 |
Correct |
169 ms |
62540 KB |
Output is correct |
104 |
Correct |
182 ms |
63476 KB |
Output is correct |
105 |
Correct |
161 ms |
62396 KB |
Output is correct |
106 |
Correct |
153 ms |
61192 KB |
Output is correct |
107 |
Correct |
152 ms |
61152 KB |
Output is correct |
108 |
Correct |
135 ms |
66240 KB |
Output is correct |
109 |
Correct |
136 ms |
66232 KB |
Output is correct |
110 |
Correct |
106 ms |
52980 KB |
Output is correct |
111 |
Correct |
123 ms |
53116 KB |
Output is correct |
112 |
Correct |
178 ms |
59892 KB |
Output is correct |
113 |
Correct |
187 ms |
59628 KB |
Output is correct |