#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int pref[mxN], in[mxN];
struct DSU{
vi sz,parent, highest;
DSU(int n) {
sz.assign(n,1);
parent.resize(n);
iota(all(parent),0);
highest.resize(n);
iota(all(highest),0);
}
void link(int a, int b) {
if(sz[a]<sz[b]) {
swap(a,b);
}
sz[a] = max(sz[a],sz[b]+1);
parent[b] = a;
if(in[highest[a]]>in[highest[b]]) {
highest[a] = highest[b];
}
}
int high(int a){
return highest[find(a)];
}
void unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
}
int find(int a) {
return a==parent[a]?a:parent[a] = find(parent[a]);
}
};
vector<pi> adj[mxN];
int cnt = 0;
void dfs(int at=0, int from=-1) {
in[at] = cnt++;
for(auto [to,haha]: adj[at]) {
if(to==from) continue;
dfs(to,at);
}
}
vi query[mxN];
void decrementlca(int a, int b) {
query[a].push_back(b);
query[b].push_back(a);
}
bitset<mxN> visited;
int k;
vi ans;
void lcadfs(int at, int from, DSU& dsu) {
visited[at]=true;
for(auto other : query[at]) {
if(visited[other]) {
// Offline LCA algorithm from: https://usaco.guide/CPH.pdf#page=181
int lca = dsu.high(other);
pref[lca]--;
}
}
for(auto [to,id]: adj[at]) {
if(to==from) continue;
lcadfs(to,at,dsu);
if(pref[to]>=k) {
ans.push_back(id+1);
}
pref[at]+=pref[to];
}
dsu.unite(at,from);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m; cin >> n >> m >> k;
for(int i=0;i<n-1;++i) {
int a,b; cin >> a >> b;
--a,--b;
adj[a].push_back({b,i});
adj[b].push_back({a,i});
}
dfs();
for(int official=0;official<m;++official) {
int s; cin >> s;
vi nes(s);
for(int& i: nes) {
cin >>i; --i;
pref[i]++;
}
sort(all(nes), [&](int a, int b){return in[a]>in[b];});
for(int i=1;i<s;++i) {
decrementlca(nes[i-1],nes[i]);
}
decrementlca(nes[0],nes.back());
}
DSU dsu(n);
lcadfs(0,0,dsu);
sort(all(ans));
cout << ans.size() << '\n';
cout << ans << '\n';
}
Compilation message
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for(auto [to,haha]: adj[at]) {
| ^
railway.cpp: In function 'void lcadfs(int, int, DSU&)':
railway.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for(auto [to,id]: adj[at]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
8 ms |
5740 KB |
Output is correct |
3 |
Correct |
8 ms |
5740 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
9 ms |
6508 KB |
Output is correct |
7 |
Correct |
9 ms |
5868 KB |
Output is correct |
8 |
Correct |
7 ms |
5740 KB |
Output is correct |
9 |
Correct |
7 ms |
5740 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
8 ms |
5740 KB |
Output is correct |
3 |
Correct |
8 ms |
5740 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
9 ms |
6508 KB |
Output is correct |
7 |
Correct |
9 ms |
5868 KB |
Output is correct |
8 |
Correct |
7 ms |
5740 KB |
Output is correct |
9 |
Correct |
7 ms |
5740 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
25 ms |
7148 KB |
Output is correct |
16 |
Correct |
25 ms |
7148 KB |
Output is correct |
17 |
Correct |
30 ms |
7148 KB |
Output is correct |
18 |
Correct |
9 ms |
6508 KB |
Output is correct |
19 |
Correct |
9 ms |
5868 KB |
Output is correct |
20 |
Correct |
26 ms |
7660 KB |
Output is correct |
21 |
Correct |
30 ms |
7660 KB |
Output is correct |
22 |
Correct |
6 ms |
5100 KB |
Output is correct |
23 |
Correct |
10 ms |
5740 KB |
Output is correct |
24 |
Correct |
8 ms |
5740 KB |
Output is correct |
25 |
Correct |
4 ms |
5100 KB |
Output is correct |
26 |
Correct |
4 ms |
5100 KB |
Output is correct |
27 |
Correct |
9 ms |
6508 KB |
Output is correct |
28 |
Correct |
9 ms |
5868 KB |
Output is correct |
29 |
Correct |
7 ms |
5740 KB |
Output is correct |
30 |
Correct |
8 ms |
5740 KB |
Output is correct |
31 |
Correct |
4 ms |
5100 KB |
Output is correct |
32 |
Correct |
4 ms |
5100 KB |
Output is correct |
33 |
Correct |
4 ms |
5100 KB |
Output is correct |
34 |
Correct |
4 ms |
5100 KB |
Output is correct |
35 |
Correct |
5 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
29028 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
93 ms |
28776 KB |
Output is correct |
4 |
Correct |
90 ms |
28416 KB |
Output is correct |
5 |
Correct |
92 ms |
29028 KB |
Output is correct |
6 |
Correct |
94 ms |
30052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
20716 KB |
Output is correct |
2 |
Correct |
102 ms |
14444 KB |
Output is correct |
3 |
Correct |
99 ms |
13804 KB |
Output is correct |
4 |
Correct |
92 ms |
13696 KB |
Output is correct |
5 |
Correct |
101 ms |
13804 KB |
Output is correct |
6 |
Correct |
73 ms |
20844 KB |
Output is correct |
7 |
Correct |
75 ms |
20728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
20716 KB |
Output is correct |
2 |
Correct |
102 ms |
14444 KB |
Output is correct |
3 |
Correct |
99 ms |
13804 KB |
Output is correct |
4 |
Correct |
92 ms |
13696 KB |
Output is correct |
5 |
Correct |
101 ms |
13804 KB |
Output is correct |
6 |
Correct |
73 ms |
20844 KB |
Output is correct |
7 |
Correct |
75 ms |
20728 KB |
Output is correct |
8 |
Correct |
93 ms |
21612 KB |
Output is correct |
9 |
Correct |
85 ms |
21612 KB |
Output is correct |
10 |
Correct |
93 ms |
29036 KB |
Output is correct |
11 |
Correct |
86 ms |
29032 KB |
Output is correct |
12 |
Correct |
74 ms |
14444 KB |
Output is correct |
13 |
Correct |
85 ms |
14444 KB |
Output is correct |
14 |
Correct |
96 ms |
13676 KB |
Output is correct |
15 |
Correct |
117 ms |
13676 KB |
Output is correct |
16 |
Correct |
91 ms |
13744 KB |
Output is correct |
17 |
Correct |
89 ms |
13676 KB |
Output is correct |
18 |
Correct |
92 ms |
13804 KB |
Output is correct |
19 |
Correct |
98 ms |
14444 KB |
Output is correct |
20 |
Correct |
75 ms |
21100 KB |
Output is correct |
21 |
Correct |
74 ms |
21096 KB |
Output is correct |
22 |
Correct |
81 ms |
21228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
8 ms |
5740 KB |
Output is correct |
3 |
Correct |
8 ms |
5740 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
9 ms |
6508 KB |
Output is correct |
7 |
Correct |
9 ms |
5868 KB |
Output is correct |
8 |
Correct |
7 ms |
5740 KB |
Output is correct |
9 |
Correct |
7 ms |
5740 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
25 ms |
7148 KB |
Output is correct |
16 |
Correct |
25 ms |
7148 KB |
Output is correct |
17 |
Correct |
30 ms |
7148 KB |
Output is correct |
18 |
Correct |
9 ms |
6508 KB |
Output is correct |
19 |
Correct |
9 ms |
5868 KB |
Output is correct |
20 |
Correct |
26 ms |
7660 KB |
Output is correct |
21 |
Correct |
30 ms |
7660 KB |
Output is correct |
22 |
Correct |
6 ms |
5100 KB |
Output is correct |
23 |
Correct |
10 ms |
5740 KB |
Output is correct |
24 |
Correct |
8 ms |
5740 KB |
Output is correct |
25 |
Correct |
4 ms |
5100 KB |
Output is correct |
26 |
Correct |
4 ms |
5100 KB |
Output is correct |
27 |
Correct |
9 ms |
6508 KB |
Output is correct |
28 |
Correct |
9 ms |
5868 KB |
Output is correct |
29 |
Correct |
7 ms |
5740 KB |
Output is correct |
30 |
Correct |
8 ms |
5740 KB |
Output is correct |
31 |
Correct |
4 ms |
5100 KB |
Output is correct |
32 |
Correct |
4 ms |
5100 KB |
Output is correct |
33 |
Correct |
4 ms |
5100 KB |
Output is correct |
34 |
Correct |
4 ms |
5100 KB |
Output is correct |
35 |
Correct |
5 ms |
5100 KB |
Output is correct |
36 |
Correct |
101 ms |
29028 KB |
Output is correct |
37 |
Correct |
4 ms |
5100 KB |
Output is correct |
38 |
Correct |
93 ms |
28776 KB |
Output is correct |
39 |
Correct |
90 ms |
28416 KB |
Output is correct |
40 |
Correct |
92 ms |
29028 KB |
Output is correct |
41 |
Correct |
94 ms |
30052 KB |
Output is correct |
42 |
Correct |
72 ms |
20716 KB |
Output is correct |
43 |
Correct |
102 ms |
14444 KB |
Output is correct |
44 |
Correct |
99 ms |
13804 KB |
Output is correct |
45 |
Correct |
92 ms |
13696 KB |
Output is correct |
46 |
Correct |
101 ms |
13804 KB |
Output is correct |
47 |
Correct |
73 ms |
20844 KB |
Output is correct |
48 |
Correct |
75 ms |
20728 KB |
Output is correct |
49 |
Correct |
93 ms |
21612 KB |
Output is correct |
50 |
Correct |
85 ms |
21612 KB |
Output is correct |
51 |
Correct |
93 ms |
29036 KB |
Output is correct |
52 |
Correct |
86 ms |
29032 KB |
Output is correct |
53 |
Correct |
74 ms |
14444 KB |
Output is correct |
54 |
Correct |
85 ms |
14444 KB |
Output is correct |
55 |
Correct |
96 ms |
13676 KB |
Output is correct |
56 |
Correct |
117 ms |
13676 KB |
Output is correct |
57 |
Correct |
91 ms |
13744 KB |
Output is correct |
58 |
Correct |
89 ms |
13676 KB |
Output is correct |
59 |
Correct |
92 ms |
13804 KB |
Output is correct |
60 |
Correct |
98 ms |
14444 KB |
Output is correct |
61 |
Correct |
75 ms |
21100 KB |
Output is correct |
62 |
Correct |
74 ms |
21096 KB |
Output is correct |
63 |
Correct |
81 ms |
21228 KB |
Output is correct |
64 |
Correct |
91 ms |
21368 KB |
Output is correct |
65 |
Correct |
113 ms |
14700 KB |
Output is correct |
66 |
Correct |
110 ms |
14572 KB |
Output is correct |
67 |
Correct |
104 ms |
14316 KB |
Output is correct |
68 |
Correct |
81 ms |
13676 KB |
Output is correct |
69 |
Correct |
82 ms |
13676 KB |
Output is correct |
70 |
Correct |
89 ms |
21736 KB |
Output is correct |
71 |
Correct |
90 ms |
21356 KB |
Output is correct |
72 |
Correct |
4 ms |
5100 KB |
Output is correct |
73 |
Correct |
8 ms |
5740 KB |
Output is correct |
74 |
Correct |
8 ms |
5740 KB |
Output is correct |
75 |
Correct |
4 ms |
5100 KB |
Output is correct |
76 |
Correct |
4 ms |
5100 KB |
Output is correct |
77 |
Correct |
11 ms |
6636 KB |
Output is correct |
78 |
Correct |
8 ms |
5868 KB |
Output is correct |
79 |
Correct |
7 ms |
5740 KB |
Output is correct |
80 |
Correct |
7 ms |
5740 KB |
Output is correct |
81 |
Correct |
4 ms |
5100 KB |
Output is correct |
82 |
Correct |
4 ms |
5100 KB |
Output is correct |
83 |
Correct |
4 ms |
5100 KB |
Output is correct |
84 |
Correct |
3 ms |
5100 KB |
Output is correct |
85 |
Correct |
3 ms |
5100 KB |
Output is correct |
86 |
Correct |
26 ms |
7148 KB |
Output is correct |
87 |
Correct |
25 ms |
7148 KB |
Output is correct |
88 |
Correct |
27 ms |
7148 KB |
Output is correct |
89 |
Correct |
9 ms |
6508 KB |
Output is correct |
90 |
Correct |
8 ms |
5868 KB |
Output is correct |
91 |
Correct |
25 ms |
7660 KB |
Output is correct |
92 |
Correct |
27 ms |
7660 KB |
Output is correct |
93 |
Correct |
4 ms |
5100 KB |
Output is correct |
94 |
Correct |
101 ms |
29176 KB |
Output is correct |
95 |
Correct |
96 ms |
28776 KB |
Output is correct |
96 |
Correct |
90 ms |
28268 KB |
Output is correct |
97 |
Correct |
101 ms |
29028 KB |
Output is correct |
98 |
Correct |
94 ms |
29924 KB |
Output is correct |
99 |
Correct |
89 ms |
13804 KB |
Output is correct |
100 |
Correct |
95 ms |
13932 KB |
Output is correct |
101 |
Correct |
123 ms |
13676 KB |
Output is correct |
102 |
Correct |
98 ms |
14444 KB |
Output is correct |
103 |
Correct |
77 ms |
20844 KB |
Output is correct |
104 |
Correct |
79 ms |
21100 KB |
Output is correct |
105 |
Correct |
79 ms |
20716 KB |
Output is correct |
106 |
Correct |
85 ms |
21740 KB |
Output is correct |
107 |
Correct |
91 ms |
21484 KB |
Output is correct |
108 |
Correct |
94 ms |
29032 KB |
Output is correct |
109 |
Correct |
92 ms |
29032 KB |
Output is correct |
110 |
Correct |
79 ms |
14444 KB |
Output is correct |
111 |
Correct |
79 ms |
14444 KB |
Output is correct |
112 |
Correct |
98 ms |
13676 KB |
Output is correct |
113 |
Correct |
88 ms |
13676 KB |
Output is correct |