#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N = 1e5+5, K = 20;
int n, m, k;
vector<int> G[N];
vector<pair<int,int > > Q[N];
int in[N], out[N], sz[N], h[N], par[N][K];
int t = 0;
void pre(int v, int p = 0)
{
par[v][0] = p;
for(int i = 1; i < K; i++)
par[v][i] = par[par[v][i-1]][i-1];
h[v] = h[p] + 1;
sz[v] = 1;
in[v] = t++;
for(int u : G[v])
if(u != p)
{
pre(u, v);
sz[v] += sz[u];
}
out[v] = t++;
}
int lca(int a, int b)
{
if(h[a] < h[b]) swap(b, a);
for(int i = K - 1; i >= 0; i--)
if(h[par[a][i]] >= h[b])
a = par[a][i];
if(a == b) return a;
for(int i = K - 1; i >= 0; i--)
if(par[a][i] != par[b][i])
a = par[a][i], b = par[b][i];
return par[a][0];
}
int ans[N];
int fcnt[N];
map<int, set<int> > cnt[N];
void dfs(int v, int p = 0)
{
int big = -1;
for(int u : G[v])
if(u != p)
{
dfs(u, v);
big = (big == -1 ? u : sz[big] < sz[u] ? u : big);
}
for(int u : G[v])
{
if(u != p && u != big)
{
for(auto e : cnt[u])
if(in[v] <= in[e.first] && out[e.first] <= out[v])
{
fcnt[big] -= cnt[big][e.first].size();
cnt[big].erase(e.first);
}
else
{
fcnt[big] -= cnt[big][e.first].size();
for(int w : e.second)
cnt[big][e.first].insert(w);
fcnt[big] += cnt[big][e.first].size();
}
}
}
if(big != -1)
swap(cnt[big], cnt[v]), fcnt[v] = fcnt[big];
for(auto i : Q[v])
{
fcnt[v] -= cnt[v][i.first].size();
cnt[v][i.first].insert(i.second);
fcnt[v] += cnt[v][i.first].size();
}
if(cnt[v].find(v) != cnt[v].end())
{
fcnt[v] -= cnt[v][v].size();
cnt[v].erase(v);
}
ans[v] = fcnt[v];
}
int main()
{
vector<pair<int,int > > e;
cin >> n >> m >> k;
for(int i = 1, u, v; i < n; i ++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
e.push_back(make_pair(u, v));
}
pre(1);
for(int i = 0; i < m; i++)
{
int sz;
cin >> sz;
vector<int> v(sz);
for(int j = 0; j < sz; j++)
cin >> v[j];
int lc = v[0];
for(int j = 1; j < sz; j++)
lc = lca(lc, v[j]);
for(int j : v)
Q[j].push_back({lc, i});
}
dfs(1);
vector<int> vec;
for(int i = 0; i < e.size(); i++)
{
if(h[e[i].first] < h[e[i].second])
swap(e[i].first, e[i].second);
if(ans[e[i].first] >= k)
vec.push_back(i + 1);
}
cout << vec.size() << endl;
for(int i : vec)
cout << i << ' ';
cout << endl;
return 0;
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < e.size(); i++)
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
11612 KB |
Output is correct |
2 |
Correct |
10 ms |
12580 KB |
Output is correct |
3 |
Correct |
9 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
11612 KB |
Output is correct |
5 |
Correct |
3 ms |
11612 KB |
Output is correct |
6 |
Correct |
11 ms |
13656 KB |
Output is correct |
7 |
Correct |
10 ms |
12892 KB |
Output is correct |
8 |
Correct |
9 ms |
12688 KB |
Output is correct |
9 |
Correct |
9 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
11796 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11796 KB |
Output is correct |
13 |
Correct |
3 ms |
11608 KB |
Output is correct |
14 |
Correct |
3 ms |
11608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
11612 KB |
Output is correct |
2 |
Correct |
10 ms |
12580 KB |
Output is correct |
3 |
Correct |
9 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
11612 KB |
Output is correct |
5 |
Correct |
3 ms |
11612 KB |
Output is correct |
6 |
Correct |
11 ms |
13656 KB |
Output is correct |
7 |
Correct |
10 ms |
12892 KB |
Output is correct |
8 |
Correct |
9 ms |
12688 KB |
Output is correct |
9 |
Correct |
9 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
11796 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11796 KB |
Output is correct |
13 |
Correct |
3 ms |
11608 KB |
Output is correct |
14 |
Correct |
3 ms |
11608 KB |
Output is correct |
15 |
Correct |
49 ms |
17748 KB |
Output is correct |
16 |
Correct |
48 ms |
17896 KB |
Output is correct |
17 |
Correct |
49 ms |
17908 KB |
Output is correct |
18 |
Correct |
12 ms |
13860 KB |
Output is correct |
19 |
Correct |
15 ms |
12888 KB |
Output is correct |
20 |
Correct |
51 ms |
19740 KB |
Output is correct |
21 |
Correct |
67 ms |
19792 KB |
Output is correct |
22 |
Correct |
3 ms |
11608 KB |
Output is correct |
23 |
Correct |
11 ms |
12636 KB |
Output is correct |
24 |
Correct |
11 ms |
12636 KB |
Output is correct |
25 |
Correct |
3 ms |
11612 KB |
Output is correct |
26 |
Correct |
3 ms |
11612 KB |
Output is correct |
27 |
Correct |
11 ms |
13660 KB |
Output is correct |
28 |
Correct |
10 ms |
12892 KB |
Output is correct |
29 |
Correct |
10 ms |
12892 KB |
Output is correct |
30 |
Correct |
9 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
11612 KB |
Output is correct |
32 |
Correct |
3 ms |
11800 KB |
Output is correct |
33 |
Correct |
3 ms |
11612 KB |
Output is correct |
34 |
Correct |
3 ms |
11612 KB |
Output is correct |
35 |
Correct |
3 ms |
11612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
54480 KB |
Output is correct |
2 |
Correct |
3 ms |
11612 KB |
Output is correct |
3 |
Correct |
207 ms |
53892 KB |
Output is correct |
4 |
Correct |
181 ms |
53832 KB |
Output is correct |
5 |
Correct |
165 ms |
52416 KB |
Output is correct |
6 |
Correct |
170 ms |
52564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
41604 KB |
Output is correct |
2 |
Correct |
163 ms |
35828 KB |
Output is correct |
3 |
Correct |
189 ms |
41764 KB |
Output is correct |
4 |
Correct |
227 ms |
50260 KB |
Output is correct |
5 |
Correct |
193 ms |
42788 KB |
Output is correct |
6 |
Correct |
152 ms |
42028 KB |
Output is correct |
7 |
Correct |
145 ms |
42016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
41604 KB |
Output is correct |
2 |
Correct |
163 ms |
35828 KB |
Output is correct |
3 |
Correct |
189 ms |
41764 KB |
Output is correct |
4 |
Correct |
227 ms |
50260 KB |
Output is correct |
5 |
Correct |
193 ms |
42788 KB |
Output is correct |
6 |
Correct |
152 ms |
42028 KB |
Output is correct |
7 |
Correct |
145 ms |
42016 KB |
Output is correct |
8 |
Correct |
151 ms |
44224 KB |
Output is correct |
9 |
Correct |
152 ms |
43960 KB |
Output is correct |
10 |
Correct |
164 ms |
52216 KB |
Output is correct |
11 |
Correct |
163 ms |
52044 KB |
Output is correct |
12 |
Correct |
122 ms |
38132 KB |
Output is correct |
13 |
Correct |
147 ms |
38088 KB |
Output is correct |
14 |
Correct |
181 ms |
38148 KB |
Output is correct |
15 |
Correct |
172 ms |
37492 KB |
Output is correct |
16 |
Correct |
221 ms |
50116 KB |
Output is correct |
17 |
Correct |
216 ms |
48684 KB |
Output is correct |
18 |
Correct |
215 ms |
46272 KB |
Output is correct |
19 |
Correct |
157 ms |
34240 KB |
Output is correct |
20 |
Correct |
160 ms |
42248 KB |
Output is correct |
21 |
Correct |
144 ms |
42540 KB |
Output is correct |
22 |
Correct |
149 ms |
42316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
11612 KB |
Output is correct |
2 |
Correct |
10 ms |
12580 KB |
Output is correct |
3 |
Correct |
9 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
11612 KB |
Output is correct |
5 |
Correct |
3 ms |
11612 KB |
Output is correct |
6 |
Correct |
11 ms |
13656 KB |
Output is correct |
7 |
Correct |
10 ms |
12892 KB |
Output is correct |
8 |
Correct |
9 ms |
12688 KB |
Output is correct |
9 |
Correct |
9 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
11796 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11796 KB |
Output is correct |
13 |
Correct |
3 ms |
11608 KB |
Output is correct |
14 |
Correct |
3 ms |
11608 KB |
Output is correct |
15 |
Correct |
49 ms |
17748 KB |
Output is correct |
16 |
Correct |
48 ms |
17896 KB |
Output is correct |
17 |
Correct |
49 ms |
17908 KB |
Output is correct |
18 |
Correct |
12 ms |
13860 KB |
Output is correct |
19 |
Correct |
15 ms |
12888 KB |
Output is correct |
20 |
Correct |
51 ms |
19740 KB |
Output is correct |
21 |
Correct |
67 ms |
19792 KB |
Output is correct |
22 |
Correct |
3 ms |
11608 KB |
Output is correct |
23 |
Correct |
11 ms |
12636 KB |
Output is correct |
24 |
Correct |
11 ms |
12636 KB |
Output is correct |
25 |
Correct |
3 ms |
11612 KB |
Output is correct |
26 |
Correct |
3 ms |
11612 KB |
Output is correct |
27 |
Correct |
11 ms |
13660 KB |
Output is correct |
28 |
Correct |
10 ms |
12892 KB |
Output is correct |
29 |
Correct |
10 ms |
12892 KB |
Output is correct |
30 |
Correct |
9 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
11612 KB |
Output is correct |
32 |
Correct |
3 ms |
11800 KB |
Output is correct |
33 |
Correct |
3 ms |
11612 KB |
Output is correct |
34 |
Correct |
3 ms |
11612 KB |
Output is correct |
35 |
Correct |
3 ms |
11612 KB |
Output is correct |
36 |
Correct |
185 ms |
54480 KB |
Output is correct |
37 |
Correct |
3 ms |
11612 KB |
Output is correct |
38 |
Correct |
207 ms |
53892 KB |
Output is correct |
39 |
Correct |
181 ms |
53832 KB |
Output is correct |
40 |
Correct |
165 ms |
52416 KB |
Output is correct |
41 |
Correct |
170 ms |
52564 KB |
Output is correct |
42 |
Correct |
141 ms |
41604 KB |
Output is correct |
43 |
Correct |
163 ms |
35828 KB |
Output is correct |
44 |
Correct |
189 ms |
41764 KB |
Output is correct |
45 |
Correct |
227 ms |
50260 KB |
Output is correct |
46 |
Correct |
193 ms |
42788 KB |
Output is correct |
47 |
Correct |
152 ms |
42028 KB |
Output is correct |
48 |
Correct |
145 ms |
42016 KB |
Output is correct |
49 |
Correct |
151 ms |
44224 KB |
Output is correct |
50 |
Correct |
152 ms |
43960 KB |
Output is correct |
51 |
Correct |
164 ms |
52216 KB |
Output is correct |
52 |
Correct |
163 ms |
52044 KB |
Output is correct |
53 |
Correct |
122 ms |
38132 KB |
Output is correct |
54 |
Correct |
147 ms |
38088 KB |
Output is correct |
55 |
Correct |
181 ms |
38148 KB |
Output is correct |
56 |
Correct |
172 ms |
37492 KB |
Output is correct |
57 |
Correct |
221 ms |
50116 KB |
Output is correct |
58 |
Correct |
216 ms |
48684 KB |
Output is correct |
59 |
Correct |
215 ms |
46272 KB |
Output is correct |
60 |
Correct |
157 ms |
34240 KB |
Output is correct |
61 |
Correct |
160 ms |
42248 KB |
Output is correct |
62 |
Correct |
144 ms |
42540 KB |
Output is correct |
63 |
Correct |
149 ms |
42316 KB |
Output is correct |
64 |
Correct |
183 ms |
43064 KB |
Output is correct |
65 |
Correct |
245 ms |
54560 KB |
Output is correct |
66 |
Correct |
212 ms |
47564 KB |
Output is correct |
67 |
Correct |
188 ms |
42864 KB |
Output is correct |
68 |
Correct |
108 ms |
34244 KB |
Output is correct |
69 |
Correct |
109 ms |
33940 KB |
Output is correct |
70 |
Correct |
158 ms |
45208 KB |
Output is correct |
71 |
Correct |
155 ms |
43688 KB |
Output is correct |
72 |
Correct |
3 ms |
11612 KB |
Output is correct |
73 |
Correct |
10 ms |
12636 KB |
Output is correct |
74 |
Correct |
9 ms |
12636 KB |
Output is correct |
75 |
Correct |
3 ms |
11608 KB |
Output is correct |
76 |
Correct |
3 ms |
11612 KB |
Output is correct |
77 |
Correct |
11 ms |
13660 KB |
Output is correct |
78 |
Correct |
10 ms |
12892 KB |
Output is correct |
79 |
Correct |
12 ms |
12692 KB |
Output is correct |
80 |
Correct |
9 ms |
12892 KB |
Output is correct |
81 |
Correct |
3 ms |
11612 KB |
Output is correct |
82 |
Correct |
2 ms |
11780 KB |
Output is correct |
83 |
Correct |
2 ms |
11608 KB |
Output is correct |
84 |
Correct |
3 ms |
11864 KB |
Output is correct |
85 |
Correct |
2 ms |
11612 KB |
Output is correct |
86 |
Correct |
49 ms |
17816 KB |
Output is correct |
87 |
Correct |
49 ms |
17752 KB |
Output is correct |
88 |
Correct |
48 ms |
17744 KB |
Output is correct |
89 |
Correct |
12 ms |
13912 KB |
Output is correct |
90 |
Correct |
10 ms |
12892 KB |
Output is correct |
91 |
Correct |
52 ms |
19944 KB |
Output is correct |
92 |
Correct |
54 ms |
19792 KB |
Output is correct |
93 |
Correct |
2 ms |
11612 KB |
Output is correct |
94 |
Correct |
166 ms |
54076 KB |
Output is correct |
95 |
Correct |
166 ms |
53956 KB |
Output is correct |
96 |
Correct |
174 ms |
53692 KB |
Output is correct |
97 |
Correct |
183 ms |
52420 KB |
Output is correct |
98 |
Correct |
163 ms |
52676 KB |
Output is correct |
99 |
Correct |
196 ms |
49136 KB |
Output is correct |
100 |
Correct |
197 ms |
48840 KB |
Output is correct |
101 |
Correct |
246 ms |
56448 KB |
Output is correct |
102 |
Correct |
151 ms |
35952 KB |
Output is correct |
103 |
Correct |
137 ms |
41960 KB |
Output is correct |
104 |
Correct |
151 ms |
42416 KB |
Output is correct |
105 |
Correct |
145 ms |
41668 KB |
Output is correct |
106 |
Correct |
154 ms |
44264 KB |
Output is correct |
107 |
Correct |
146 ms |
44024 KB |
Output is correct |
108 |
Correct |
145 ms |
52168 KB |
Output is correct |
109 |
Correct |
147 ms |
52160 KB |
Output is correct |
110 |
Correct |
122 ms |
38136 KB |
Output is correct |
111 |
Correct |
120 ms |
38076 KB |
Output is correct |
112 |
Correct |
159 ms |
38340 KB |
Output is correct |
113 |
Correct |
166 ms |
37832 KB |
Output is correct |