제출 #1268409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268409		_wesstiov_	Railway (BOI17_railway)	C++20	100 / 100	69 ms	24584 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<ii> vex , adj[MXN + 5];
int in[MXN + 5] , out[MXN + 5] , timer , up[MXN + 5][LG + 2];
int dp[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){
    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 dfs1(int u,int par){
    for (ii v : adj[u]){
        if (v.fi == par) continue;
        dfs1(v.fi , u);
        dp[u] += dp[v.fi];
        if (dp[v.fi] / 2 >= 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());
        vex.emplace_back(vex[0]);

        for (int j = 0; j + 1 < vex.size() ; j++){
            dp[vex[j].sc]++;
            dp[vex[j + 1].sc]++;
            dp[lca(vex[j].sc , vex[j + 1].sc)] -= 2;
        }
        vex.clear();
    }

    dfs1(1 , 1);

    sort(ANS.begin() , ANS.end());
    cout << ANS.size() <<'\n';
    for (int u : ANS) cout << u <<' ';
}

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