Submission #996595

#	Time	Username	Problem	Language	Result	Execution time	Memory
996595		MarwenElarbi	Railway (BOI17_railway)	C++17	100 / 100	112 ms	29524 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
int n,m,k;
vector<pair<int,int>> adj[nax];
int timer=-1;
pair<int,int> tin[nax];
int tab[nax];
int dp[nax][20];
int depth[nax];
int ans[nax];
int pre[nax];
bool compare(int x,int y){
    return tin[x].fi<tin[y].fi;
}
void euler(int x,int p){
    tin[x].fi=++timer;
    for (int i = 1; i < 20; ++i)
    {
        dp[x][i]=dp[dp[x][i-1]][i-1];
    }
    for(auto u:adj[x]){
        if(u.fi==p) continue;
        dp[u.fi][0]=x;
        depth[u.fi]=depth[x]+1;
        euler(u.fi,x);
    }
    tin[x].se=timer;
}
int jump(int x,int d){
    for (int i = 19; i >= 0; --i)
    {
        if(d&(1<<i)) x=dp[x][i];
    }
    return x;
}
int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);
    x=jump(x,depth[x]-depth[y]);
    if(x==y) return x;
    for (int i = 19; i >= 0; --i)
    {
        if(dp[x][i]!=dp[y][i]){
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];
}
int res;
void dfs(int x,int p){
    for(auto u:adj[x]){
        if(u.fi==p) continue;
        dfs(u.fi,x);
        if(pre[u.fi]>=2*k){
            ans[u.se]=1;
            res++;
        }
        pre[x]+=pre[u.fi];
    }
    //cout <<x<<" "<<pre[x]<<endl;
}
int main(){
    cin>>n>>m>>k;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb({y,i});
        adj[y].pb({x,i});
    }
    euler(0,-1);
    for (int i = 0; i < m; ++i)
    {
        int s;
        cin>>s;
        vector<int> state(s);
        for (int j = 0; j < s; ++j)
        {
            cin>>state[j];
            state[j]--;
        }
        sort(state.begin(),state.end(),compare);
        for (int j = 0; j < s; ++j)
        {
            int l=lca(state[j],state[(j+1)%s]);
            //cout <<state[j]<<" "<<state[(j+1)%s]<<" "<<l<<endl;
            pre[l]-=2;
            pre[state[j]]++;
            pre[state[(j+1)%s]]++;
        }
    }
    dfs(0,-1);
    cout <<res<<endl;
    for (int i = 0; i < n-1; ++i)
    {
        if(ans[i]) cout <<i+1<<" ";
    }
}

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