Submission #1156145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156145		k12_khoi	Railway (BOI17_railway)	C++17	100 / 100	201 ms	45768 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int N=1e5+5;
int n,q,k,x,y,p[N][22],m,t,H[N]; vector <pii> adj[N]; vector <int> del[N],ve; set <int> se[N];
void dfs(int u,int par)
{
    for (pii v:adj[u])
    if (v.X!=par)
    {
        H[v.X]=H[u]+1;
        p[v.X][0]=u;
        dfs(v.X,u);
    }
}
int lca(int a,int b)
{
    if (H[a]<H[b]) swap(a,b);
    for (int j=20;j>=0;j--)
    if (H[p[a][j]]>=H[b])
    {
        a=p[a][j];
    }
    if (a==b) return a;
    for (int j=20;j>=0;j--)
    if (p[a][j]!=p[b][j])
    {
        a=p[a][j];
        b=p[b][j];
    }
    return p[a][0];
}
void calc(int u,int par)
{
    for (pii v:adj[u])
    if (v.X!=par)
    {
        calc(v.X,u);
        if (se[v.X].size()>=k) ve.push_back(v.Y);
        if (se[v.X].size()>se[u].size()) swap(se[v.X],se[u]);
        for (int i:se[v.X])
        se[u].insert(i);
    }
    for (int v:del[u])
    se[u].erase(se[u].find(v));
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> q >> k;
    for (int i=1;i<=n-1;i++)
    {
        cin >> x >> y;
        adj[x].push_back(make_pair(y,i));
        adj[y].push_back(make_pair(x,i));
    }
    H[1]=1;
    dfs(1,-1);
    for (int j=1;j<=20;j++)
    for (int i=1;i<=n;i++)
    p[i][j]=p[p[i][j-1]][j-1];
    for (int i=1;i<=q;i++)
    {
        cin >> m;
        t=n+1;
        for (int j=1;j<=m;j++)
        {
            cin >> x;
            se[x].insert(i);
            if (t==n+1) t=x;
            else t=lca(t,x);
        }
        del[t].push_back(i);
    }
    calc(1,-1);
    sort(ve.begin(),ve.end());
    cout << ve.size() << '\n';
    for (int i=0;i<ve.size();i++)
    cout << ve[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