Submission #908088

#	Time	Username	Problem	Language	Result	Execution time	Memory
908088		anarch_y	Railway (BOI17_railway)	C++17	100 / 100	280 ms	60260 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define pb push_back
#define sz(x) (int)x.size()
 
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);
    }
    for(auto e: rem[s]) add[s].erase(e);
    num[s] = sz(add[s]);
}
 
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]);
        }
        rem[c].insert(j);
        for(auto e: v) add[e].insert(j);
    }
    dfs(1, 0);
 
    vector<int> ans;
    for(int i=0; i<n-1; i++){
        auto &[a, b] = edges[i];
        if(L.depth[b] < L.depth[a]) swap(a, b);
        if(num[b] >= k) ans.pb(i+1);
    }
    cout << sz(ans) << "\n";
    for(auto 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