Submission #896372

#	Time	Username	Problem	Language	Result	Execution time	Memory
896372		AlphaMale06	Railway (BOI17_railway)	C++14	100 / 100	79 ms	27004 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 1e5+3;

vector<int> adj[N];
int p[N][17];
int tin[N], tout[N];
int timer=-1;
void dfs(int v, int par){
    p[v][0]=par;
    for(int i=1; i<17; i++){
        p[v][i]=p[p[v][i-1]][i-1];
    }
    timer++;
    tin[v]=timer;
    for(int to : adj[v]){
        if(to!=par)dfs(to, v);
    }
    tout[v]=timer;
}

bool anc(int a, int b){
    return (tin[a]<=tin[b] && tout[a]>=tout[b]);
}

int lca(int a, int b){
    if(anc(a, b))return a;
    if(anc(b, a))return b;
    int ret=a;
    for(int i=16; i>=0; i--){
        if(!anc(p[ret][i], b)){
            ret=p[ret][i];
        }
    }
    return p[ret][0];
}

struct minister{
    int n;
    vector<pair<int, int>> nodes;
};

minister a[N/2];
int val[N];

int bring=0;


void dfs2(int v, int par){
    for(int to : adj[v]){
        if(to!=par){
            dfs2(to, v);
            val[v]+=bring;
            bring=0;
        }
    }
    bring+=val[v];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> edges(n-1);
    for(int i=0; i< n-1; i++){
        cin >> edges[i].F >> edges[i].S;
        adj[edges[i].F].pb(edges[i].S);
        adj[edges[i].S].pb(edges[i].F);
    }
    dfs(1, 0);
    tin[0]=-1;
    tout[0]=1e9;
    for(int i=0; i< n-1; i++){
        if(anc(edges[i].S, edges[i].F))swap(edges[i].F, edges[i].S);
    }
    for(int i = 0; i< m; i++){
        cin >> a[i].n;
        for(int j=0; j< a[i].n; j++){
            int x;
            cin >> x;
            a[i].nodes.pb({tin[x], x});
        }
        sort(a[i].nodes.begin(), a[i].nodes.end());
        int lc=a[i].nodes[0].S;
        for(int j=0; j< a[i].n-1; j++)val[lca(a[i].nodes[j].S, a[i].nodes[j+1].S)]--;
        for(int j=0; j<a[i].n; j++)val[a[i].nodes[j].S]++;
        for(int j=1; j<a[i].n; j++)lc=lca(lc, a[i].nodes[j].S);
        val[lc]--;
    }
    dfs2(1, 0);
    vector<int> ans;
    for(int i=0; i< n-1; i++){
        if(val[edges[i].S]>=k)ans.pb(i+1);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(int e : ans)cout << e << ' ';
}

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