| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 205780 | ly20 | Railway (BOI17_railway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
int dp[MAXN][MAXK], prof[MAXN];
vector <int> grafo[MAXN];
void dfs(int v, int p) {
dp[v][0] = p;
for(int i = 1; i < MAXK; i++) {
dp[v][i] = dp[dp[v][i - 1]][i - 1];
}
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(viz == p) continue;
prof[viz] = prof[v] + 1;
dfs(viz, v);
}
}
int lca(int a, int b) {
if(prof[a] > prof[b]) swap(a, b);
int d = prof[b] - prof[a];
for(int i = 0; i < MAXK; i++) {
if(d & (1 << i)) b = dp[b][i];
}
if(a == b) return a;
for(int i = MAXK - 1; i >= 0; i--) {
if(dp[a][i] != dp[b][i]) {
a = dp[a][i]; b = dp[b][i];
}
}
return dp[a][0];
}
map < pair < int, int >, int > mp;
int marc[MAXN], cont[MAXN];
bool dfs1(int v, int p) {
//printf("%d\n", v);
bool ok = false;
if(marc[v] == 1) ok = true;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
//printf("%d %d\n", v, viz);
if(viz == p) continue;
//printf("oi\n");
if(dfs1(viz, v)) ok = true;
}
if(ok) {
cont[v]++;
//printf("%d++\n", v);
}
return ok;
}
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i < n; i++) {
int a, b;
scanf("%d %d", &a, &b);
grafo[a].push_back(b); grafo[b].push_back(a);
mp[make_pair(a, b)] = i; mp[make_pair(b, a)] = i;
}
dfs(1, 1);
for(int i = 0; i < m; i++) {
vector < int > v;
int a;
scanf("%d", &a);
int lc;
scanf("%d", &lc);
v.push_back(lc);
marc[lc] = 1;
for(int j = 1; j < a; j++) {
int b;
scanf("%d", &b);
marc[b] = 1;
v.push_back(b);
lc = lca(lc, b);
}
//printf("%d\n", lc);
dfs1(lc, lc);
cont[lc]--;
for(int j = 0; j < a; j++) {
marc[v[j]] = 0;
}
v.clear();
}
vector <int> v;
for(int i = 1; i <= n; i++) {
if(cont[i] >= k) v.push_back(mp[make_pair(i, dp[i][0])]);
}
printf("%d\n", v.size());
sort(v.begin(), v.end());
for(int i = 0; i < v.size() - 1; i++) printf("%d ", v[i]);
if(v.size > 0) printf("%d\n", v[v.size() - 1]);
return 0;
}