제출 #1353091

#제출 시각아이디문제언어결과실행 시간메모리
1353091vahagngRailway (BOI17_railway)C++20
23 / 100
1096 ms21076 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, k, up[N][19], depth[N], val[N], tin[N], timer, deg[N];
vector<pair<int,int>> adj[N];
pair<int,int> par[N];
bool marked[N];

void dfs(int node, int parent){
    up[node][0] = parent;
    for(int i = 1; i < 19; i++){
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for(auto [u, i] : adj[node]){
        if(u == parent) continue;
        depth[u] = depth[node] + 1;
        par[u] = {node, i};
        dfs(u, node);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int i = 0; i < 19; i++){
        if(d & (1 << i)){
            u = up[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 18; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void upd(int node, int p){
    while(node != p){
        marked[par[node].second] = 1;
        node = par[node].first;
    }
}

int main(){
    cin >> n >> m >> k;
    vector<pair<int,int>> edges;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 1);
    for(int i = 0; i < m; i++){
        int s;
        cin >> s;
        vector<int> v;
        while(s--){
            int u;
            cin >> u;
            v.push_back(u);
        }
        int l = v[0];
        for(auto j : v) l = lca(l, j);
        for(auto j : v){
            upd(j, l);
        }
        for(int j = 1; j < n; j++){
            val[j] += marked[j];
            marked[j] = 0;
        }
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 0; j < 18; j++){
    //         cerr << "up[" << i << "][" << j << "] = " << up[i][j] << endl;
    //     }
    // }
    vector<int> res;
    for(int i = 0; i < n - 1; i++){
        if(val[i + 1] >= k){
            res.push_back(i + 1);
        }
    }
    cout << res.size() << endl;
    for(auto i : res) cout << i << ' ';
    cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...