제출 #907453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907453		anarch_y	Railway (BOI17_railway)	C++17	0 / 100	1069 ms	524288 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct LCA{
    int n; 
    vector<vector<int>> adj, up;
    vector<int> depth;

    LCA(int _n){
        n = _n;
        up.resize(n+1);
        for(int i=0; i<=n; i++){
            up[i].resize(20, 0);
        }
        adj.resize(n+1);
        depth.resize(n+1);
    }

    void ae(int a, int b){
        adj[a].pb(b);
        adj[b].pb(a);
    }

    void dfs(int s, int p){
        depth[s] = depth[p]+1;
        up[s][0] = p;
        for(auto u: adj[s]){
            if(u == p) continue;
            dfs(u, s);
        }
    }

    void init(){
        depth[0] = 0;
        dfs(1, 0);
        for(int j=1; j<20; j++){
            for(int i=1; i<=n; i++){
                up[i][j] = up[up[i][j-1]][j-1];
            }
        }    
    }

    int jump(int x, int d){
        for(int i=0; i<20; i++){
            if(d & (1<<i)) x = up[x][i];
        }
        return x;
    }
    
    int lca(int a, int b){
        if(depth[a] < depth[b]) swap(a, b);
        a = jump(a, depth[a]-depth[b]);

        if(a == b) return a; 
        
        for(int i=19; i>=0; i--){
            if(up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
    
	int dist(int a, int b){
		int c = lca(a, b);
		int d = depth[a]+depth[b]-2*depth[c];
		return d;
	}
};

const int maxn = 100001;
vector<int> adj[maxn];
set<int> add[maxn], rem[maxn];
int num[maxn];

void dfs(int s, int p){
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        if(sz(add[u]) > sz(add[s])) swap(add[u], add[s]);
        for(auto e: add[u]) add[s].insert(e);
    }
    num[s] = sz(add[s]);
    for(auto e: rem[s]) add[s].erase(e);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    vector<pair<int, int>> edges(n-1);

    LCA L(n);
    for(int i=0; i<n-1; i++){
        int a, b; cin >> a >> b;
        L.ae(a, b);
        adj[a].pb(b); adj[b].pb(a);
        edges[i] = {a, b};
    }
    L.init();

    for(int j=1; j<=m; j++){
        int s; cin >> s;
        vector<int> v(s);
        for(int i=0; i<s; i++) cin >> v[i];
        int c = L.lca(v[0], v[1]);
        for(int i=2; i<s; i++){
            c = L.lca(c, v[i]);
        }
        add[c].insert(j);
        for(auto e: v){
            while(e != c){
                add[e].insert(j);
                e = L.up[e][0];
            }
        }
    }
    for(int i=1; i<=n; i++) num[i] = sz(add[i]);

    vector<int> ans;
    for(int i=0; i<n-1; i++){
        auto &[a, b] = edges[i];
        if(num[a] >= k and num[b] >= k) ans.pb(i+1);
    }
    cout << sz(ans) << "\n";
    for(auto e: ans) cout << e << ' ';
}

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