Submission #1268399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268399		_wesstiov_	Railway (BOI17_railway)	C++20	29 / 100	71 ms	28608 KiB

railway

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define sc second
#define ii pair<int ,int>

const int MXN = 1e5;
const int LG = 16;

int n , m , k;
vector<int>  nadj[MXN + 5];
vector<ii> vex , adj[MXN + 5];
int root;
int in[MXN + 5] , out[MXN + 5] , timer , up[MXN + 5][LG + 2];
int dp[MXN + 5] , f[MXN + 5];
vector<int> ANS;

void dfs(int u,int par){
    in[u] = ++timer;
    up[u][0] = par;

    for (int i = 1; i <= LG ; i++) up[u][i] = up[up[u][i - 1]][i - 1];

    for (ii v : adj[u]){
        if (v.fi == par) continue;
        dfs(v.fi , u);
    }

    out[u] = timer;
}

bool isAnc(int u,int v){
  if (u == 0 || v == 0)
    return 1;
    return (in[u] <= in[v] and out[v] <= out[u]);
}

int lca(int u,int v){
    if (isAnc(u , v)) return u;
    if (isAnc(v , u)) return v;

    for (int i = LG ;i >= 0; i--){
        if (!isAnc(up[u][i] , v)) u = up[u][i];
    }

    return up[u][0];
}

void build(){
    stack<int> s;

    for (ii v : vex){
        while (!s.empty() and !isAnc(s.top() , v.sc)){
            s.pop();
        }

        if (!s.empty()){
            nadj[v.sc].emplace_back(s.top());
            nadj[s.top()].emplace_back(v.sc);
        }
        s.push(v.sc);
    }
}

void dfs1(int u,int par){
    f[u] = 1;

    for (int v : nadj[u]){
        if (v == par) continue;

        dfs1(v , u);
        f[u] += f[v];
    }

    dp[u]++;
    if (u == par){
        dp[u] -= f[u] + 1;
    }else if (f[u] > 1) dp[u] -= f[u];
}

void dfs2(int u,int par){
    for (ii v : adj[u]){
        if (v.fi == par) continue;
        dfs2(v.fi , u);
        dp[u] += dp[v.fi];
        if (dp[v.fi] >= k) {
            ANS.emplace_back(v.sc);
        }
    }
}

signed main(){
    cin.tie(0)->ios_base::sync_with_stdio(0);
//    freopen("SPEED.INP" , "r" , stdin);
//    freopen("SPEED.OUT" , "w" , stdout);

    cin >> n >> m >> k;
    for (int i = 1; i < n ;i++){
        int u , v; cin >> u >> v;
        adj[u].emplace_back(v , i);
        adj[v].emplace_back(u , i);
    }

    dfs(1 , 1);

    for (int i = 1; i <= m ;i++){
        int s; cin >> s;
        for (int j = 1; j <= s ; j++){
            int u; cin >> u;
            vex.emplace_back(in[u] , u);
        }

        sort(vex.begin() , vex.end());
        for (int j = 0; j + 1 < s ; j++){
            int u = lca(vex[j].sc , vex[j + 1].sc);
            vex.emplace_back(in[u] , u);
        }

        sort(vex.begin() , vex.end());
        vex.resize(unique(vex.begin() , vex.end()) - vex.begin());

        build();
        dfs1(vex[0].sc , vex[0].sc);

        for (ii v : vex){
            nadj[v.sc].clear();
            f[v.sc] = 0;
        }
        vex.clear();
    }
    dfs2(1 , 1);
    sort(ANS.begin() , ANS.end());
    cout << ANS.size() <<'\n';
    for (int u : ANS) cout << u <<' ';
}

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