#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define F first
#define S second
const int N = 1e5 + 10;
const int inf = 2e9;
const int mod = 998244353;
const int lg = 17;
using namespace std;
int up[N][lg],in[N],out[N],timer = 0,pr[N],ans[N];
vector<int>g[N];
bool inn(int u,int v) {
//dal je v u u
if(in[u] <= in[v] && out[u] >= out[v]) return true;
return false;
}
int lca(int u,int v) {
if(inn(u,v)) return u;
if(inn(v,u)) return v;
for(int j = lg - 1; j >= 0; j--) {
if(up[u][j] == 0) continue;
if(!inn(up[u][j],v)) u = up[u][j];
}
return up[u][0];
}
void dfs(int x,int par) {
pr[x] = par;
up[x][0] = par;
in[x] = ++timer;
for(auto X : g[x]) {
if(X != par) {
dfs(X,x);
}
}
out[x] = timer;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,k;
cin >> n >> m >> k;
map<pair<int,int>,int>index;
for(int i = 1; i <= n - 1; i++) {
int u,v;
cin >> u >> v;
index[{u,v}] = i;
index[{v,u}] = i;
g[u].pb(v);
g[v].pb(u);
}
dfs(1,0);
for(int j = 1; j < lg; j++) {
for(int i = 1; i <= n; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
for(int i = 1; i <= m; i++) {
int s;
cin >> s;
vector<int>b(s + 1);
for(int j = 1; j <= s; j++) cin >> b[j];
int LCA = lca(b[1],b[2]);
for(int j = 3; j <= s; j++) LCA = lca(LCA,b[j]);
bool was[n + 1];
for(int j = 1; j <= n; j++) was[j] = false;
for(int j = 1; j <= s; j++) {
while(b[j] != LCA) {
was[b[j]] = true;
b[j] = pr[b[j]];
}
}
for(int j = 1; j <= n; j++) {
if(was[j]) {
ans[index[{pr[j],j}]] += 1;
}
}
}
vector<int>rez;
for(int i = 1; i <= n - 1; i++) if(ans[i] >= k) rez.pb(i);
cout << rez.size() << "\n";
for(auto X : rez) cout << X << " ";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
9 ms |
5212 KB |
Output is correct |
3 |
Correct |
9 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
83 ms |
5548 KB |
Output is correct |
7 |
Correct |
9 ms |
5212 KB |
Output is correct |
8 |
Correct |
10 ms |
5368 KB |
Output is correct |
9 |
Correct |
11 ms |
5212 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
2 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
9 ms |
5212 KB |
Output is correct |
3 |
Correct |
9 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
83 ms |
5548 KB |
Output is correct |
7 |
Correct |
9 ms |
5212 KB |
Output is correct |
8 |
Correct |
10 ms |
5368 KB |
Output is correct |
9 |
Correct |
11 ms |
5212 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
2 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
37 ms |
5696 KB |
Output is correct |
16 |
Correct |
36 ms |
5664 KB |
Output is correct |
17 |
Correct |
33 ms |
5724 KB |
Output is correct |
18 |
Correct |
253 ms |
5560 KB |
Output is correct |
19 |
Correct |
27 ms |
5208 KB |
Output is correct |
20 |
Correct |
29 ms |
5724 KB |
Output is correct |
21 |
Correct |
29 ms |
5724 KB |
Output is correct |
22 |
Correct |
1 ms |
2648 KB |
Output is correct |
23 |
Correct |
9 ms |
5212 KB |
Output is correct |
24 |
Correct |
9 ms |
5212 KB |
Output is correct |
25 |
Correct |
1 ms |
2652 KB |
Output is correct |
26 |
Correct |
1 ms |
2652 KB |
Output is correct |
27 |
Correct |
83 ms |
5536 KB |
Output is correct |
28 |
Correct |
9 ms |
5212 KB |
Output is correct |
29 |
Correct |
10 ms |
5212 KB |
Output is correct |
30 |
Correct |
11 ms |
5368 KB |
Output is correct |
31 |
Correct |
1 ms |
2652 KB |
Output is correct |
32 |
Correct |
1 ms |
2652 KB |
Output is correct |
33 |
Correct |
1 ms |
2652 KB |
Output is correct |
34 |
Correct |
1 ms |
2652 KB |
Output is correct |
35 |
Correct |
1 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1057 ms |
32612 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1050 ms |
30620 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1050 ms |
30620 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
9 ms |
5212 KB |
Output is correct |
3 |
Correct |
9 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
83 ms |
5548 KB |
Output is correct |
7 |
Correct |
9 ms |
5212 KB |
Output is correct |
8 |
Correct |
10 ms |
5368 KB |
Output is correct |
9 |
Correct |
11 ms |
5212 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
2 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
37 ms |
5696 KB |
Output is correct |
16 |
Correct |
36 ms |
5664 KB |
Output is correct |
17 |
Correct |
33 ms |
5724 KB |
Output is correct |
18 |
Correct |
253 ms |
5560 KB |
Output is correct |
19 |
Correct |
27 ms |
5208 KB |
Output is correct |
20 |
Correct |
29 ms |
5724 KB |
Output is correct |
21 |
Correct |
29 ms |
5724 KB |
Output is correct |
22 |
Correct |
1 ms |
2648 KB |
Output is correct |
23 |
Correct |
9 ms |
5212 KB |
Output is correct |
24 |
Correct |
9 ms |
5212 KB |
Output is correct |
25 |
Correct |
1 ms |
2652 KB |
Output is correct |
26 |
Correct |
1 ms |
2652 KB |
Output is correct |
27 |
Correct |
83 ms |
5536 KB |
Output is correct |
28 |
Correct |
9 ms |
5212 KB |
Output is correct |
29 |
Correct |
10 ms |
5212 KB |
Output is correct |
30 |
Correct |
11 ms |
5368 KB |
Output is correct |
31 |
Correct |
1 ms |
2652 KB |
Output is correct |
32 |
Correct |
1 ms |
2652 KB |
Output is correct |
33 |
Correct |
1 ms |
2652 KB |
Output is correct |
34 |
Correct |
1 ms |
2652 KB |
Output is correct |
35 |
Correct |
1 ms |
2816 KB |
Output is correct |
36 |
Execution timed out |
1057 ms |
32612 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |