Submission #1096667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096667		Top1BUCODE	Railway (BOI17_railway)	C++17	29 / 100	59 ms	28236 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;
const int K=22;
int n,m,x,y,k,sz[N],h,H[N],p[N][K],t,c[N],e[N]; vector <int> g,w[N];; vector <pii> adj[N]; bool check[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;
        e[v.X]=v.Y;
        sz[u]+=sz[v.X];
        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);
        sz[u]+=sz[v.X];
        if (sz[v.X]>=k) g.push_back(v.Y);
    }
}
void lcb(int a)
{
    while (!check[a])
    {
        check[a]=true;
        g.push_back(e[a]);
        a=p[a][0];
    }
}
bool cmp(int x,int y)
{
    return H[x]>H[y];
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> 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 j=1;j<=m;j++)
    {
        cin >> y;
        for (int i=1;i<=y;i++)
        {
            cin >> x;
            w[j].push_back(x);
        }
        t=max(t,y);
    }
    if (t==2)
    {
        for (int i=1;i<=m;i++)
        if (w[i].size()==2)
        {
            sz[w[i][0]]++;
            sz[w[i][1]]++;
            sz[lca(w[i][1],w[i][0])]-=2;
        }
      calc(1,-1);
    }
    else
    {
        t=0;
        for (int i=1;i<=m;i++)
        for (int j:w[i])
        sz[j]++;
        for (int i=1;i<=n;i++)
        if (sz[i]>=k)
        {
            t++;
            c[t]=i;
        }
        sort(c+1,c+t+1,cmp);
        x=c[1];
        for (int i=2;i<=t;i++)
        x=lca(x,c[i]);
        check[x]=true;
        for (int i=1;i<=t;i++)
        if (!check[c[i]]) lcb(c[i]);
    }
    sort(g.begin(),g.end());
    cout << g.size() << "\n";
    for (int i:g)
    cout << i << ' ';
}

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