Submission #1260641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260641		trinhvtuan	Railway (BOI17_railway)	C++17	100 / 100	150 ms	45016 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef pair<int,int>i2;
long long c,d,x,y,z,n,q,m;
int i,j,k;
vector<i2>a[N];
vector<int>g[N],kq;
int up[N][22],h[N],b[N],canh[N];
set<int>st[N];
void dfs(int u)
{
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        if (v==up[u][0]) continue;
        h[v]=h[u]+1;
        up[v][0]=u;
        canh[v]=a[u][i].first;
        for (int j=1;j<=20;j++)
        up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);
    }
}
int lca(int u,int v)
{
    if (h[u]!=h[v])
    {
        if (h[u]<h[v]) swap(u,v);
        int k=h[u]-h[v];
        for (int i=0;(1<<i)<=k;i++)
        if (k>>i&1) u=up[u][i];
    }
    if (u==v) return u;
    int k=__lg(h[u]);
    for (int i=k;i>=0;i--)
    if (up[u][i]!=up[v][i])
    {
        u=up[u][i]; v=up[v][i];
    }
    return up[u][0];
}
void dfs1(int u,int pre)
{
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        if (v==pre) continue;
        dfs1(v,u);
        if (st[u].size()<st[v].size()) swap(st[u],st[v]);
        for (auto id:st[v])
        st[u].insert(id);
    }
    for (int i=0;i<g[u].size();i++)
    {
        int x=g[u][i];
        st[u].erase(st[u].find(x));
    }
    if (st[u].size()>=k) kq.push_back(canh[u]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q>>k;
    for (int i=1;i<n;i++)
    {
        cin>>x>>y;
        a[x].push_back({i,y});
        a[y].push_back({i,x});
    }
    dfs(1);
    for (int rep=1;rep<=q;rep++)
    {
        cin>>m;
        for (int i=1;i<=m;i++)
        {
            cin>>b[i];
            if (i==1) c=b[i]; else c=lca(c,b[i]);
        }
        for (int i=1;i<=m;i++)
        {
            st[b[i]].insert(rep);
        }
        g[c].push_back(rep);
    }
    dfs1(1,0);
    sort(kq.begin(),kq.end());
    cout<<kq.size()<<"\n";
    for (int i=0;i<kq.size();i++)
    cout<<kq[i]<<" ";
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25