| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 714674 | Melika0gh | 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;
typedef long long ll;
typedef long double ld;
#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int maxn = 2e5 + 10, mood = 1e9 + 7, maxsq = 400, maxlg = 21;
//const int mood2 = 97277821, mood3 = 34098487, base = 31;
vector<int> adj[maxn];
vector<pair<int, int> > edge;
int anc[maxn][maxlg];
int st[maxn], ft[maxn], cnt[maxn], h[maxn];
int n, m, k, t;
void Dfs(int v = 1, int par = -1)
{
st[v] = ++t;
for(int i = 1; i < maxlg; i++)
{
anc[v][i] = anc[anc[v][i-1]][i-1];
}
for(auto u : adj[v]) if(u != par)
{
h[u] = h[v] + 1;
anc[u][0] = v;
Dfs(u, v);
}
ft[v] = t;
}
void Dfs2(int v = 1, int par = -1)
{
for(auto u : adj[v]) if(u != par)
{
Dfs2(u, v);
cnt[v] += cnt[u];
}
return;
}
int Up(int u, int d)
{
for(int i = 0; i < maxlg; i++)
{
if((d >> i) & 1)
u = anc[u][i];
}
return u;
}
int Lca(int u, int v)
{
if(h[u] < h[v])
swap(u, v);
u = Up(u, h[u] - h[v]);
for(int i = maxlg - 1; i >= 0; i--)
{
if(anc[u][i] != anc[v][i])
{
u = anc[u][i];
v = anc[v][i];
}
}
if(v == u)
return v;
return anc[v][0];
}
bool cmp(int a, int b)
{
return st[a] < st[b];
}
int main()
{
sync;
cin >> n >> m >> k;
for(int i = 0; i < n-1; i++)
{
int u, v;
cin >> u >> v;
edge.pb(mp(u, v));
adj[u].pb(v);
adj[v].pb(u);
}
Dfs();
for(int i = 0; i < m; i++)
{
vector<int> vec;
int s;
cin >> s;
for(int j = 0; j < s; j++)
{
int x;
cin >> x;
vec.pb(x);
}
sort(vec.begin(), vec.end(), cmp);
for(int j = 0; j < s; j++)
{
int v = vec[j], u = vec[(j+1) % s];
cnt[v]++;
int lca = Lca(v, u);
cnt[lca]--;
}
}
Dfs2();
vector<int> ans;
for(int i = 0; i < n-1; i++)
{
int u = edge[i].fi, v = edge[i].se;
if(h[u] < h[v])
swap(u, v);
if(cnt[u] >= k)
{
ans.pb(i+1);
}
}
cout << ans.size() << '\n';
for(int x : ans)
cout << x << ' ';
cout << '\n';
}