Submission #940071

#	Time	Username	Problem	Language	Result	Execution time	Memory
940071		phoenix0423	Railway (BOI17_railway)	C++17	100 / 100	266 ms	46412 KiB

railway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
int n, m, k;
int succ[maxn][18], dep[maxn];
int sz[maxn], head[maxn], in[maxn], dfn = 0;
vector<pll> adj[maxn];
vector<int> ans;

void dfs(int pos, int prev){
    sz[pos] = 1;
    succ[pos][0] = prev;
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto &k : adj[pos]){
        int x, id;
        tie(x, id) = k;
        if(x == prev) continue;
        adj[x].erase(find(adj[x].begin(), adj[x].end(), pll(pos, id)));
        dep[x] = dep[pos] + 1;
        dfs(x, pos);
        sz[pos] += sz[x];
        if(sz[x] > sz[adj[pos][0].f]) swap(k, adj[pos][0]);
    }
}

void decompose(int pos, int h){
    head[pos] = h;
    in[pos] = ++dfn;
    for(auto [x, id] : adj[pos]){
        if(pll(x, id) == adj[pos][0]) decompose(x, h);
        else decompose(x, x);
    }
}

int lift(int b, int s){
    for(int i = 17; i >= 0; i--){
        if(s & (1 << i)) b = succ[b][i];
    }
    return b;
}
int find_lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    b = lift(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int i = 17; i >= 0; i--){
        if(succ[a][i] != succ[b][i]) a = succ[a][i], b = succ[b][i];
    }
    return succ[a][0];
}

int st[maxn * 4];
void push(int v){
    st[v * 2] += st[v], st[v * 2 + 1] += st[v], st[v] = 0;
}
void upd(int l, int r, int val, int v = 1, int L = 0, int R = n){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        st[v] += val;
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
}

int qry(int pos, int v = 1, int l = 0, int r = n){
    if(l == r) return st[v];
    push(v);
    int m = (l + r) / 2;
    if(pos <= m) return qry(pos, v * 2, l, m);
    else return qry(pos, v * 2 + 1, m + 1, r);
}
void path_aggregate(int a, int b, int val){
    // dep[a] < dep[b], lca(a, b) = a
    while(head[b] != head[a]){
        upd(in[head[b]], in[b], val);
        b = succ[head[b]][0];
    }
    upd(in[a], in[b], val);
}

void dfs2(int pos, int id = -1){
    if(id != -1){
        if(qry(in[pos]) >= k) ans.pb(id);
    }
    for(auto [x, id] : adj[pos]){
        dfs2(x, id);
    }
}
signed main(void){
    // fastio;
    cin>>n>>m>>k;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].eb(b, i), adj[b].eb(a, i);
    }
    dfs(0, 0);
    decompose(0, 0);
    for(int i = 0; i < m; i++){
        int d;
        cin>>d;
        vector<int> a(d);
        for(int j = 0; j < d; j++) cin>>a[j], a[j] --;
        sort(a.begin(), a.end(), [&](int x, int y){ return in[x] < in[y];});
        a.erase(unique(a.begin(), a.end()), a.end());
        if(d < 2) continue;
        int glca = find_lca(a[0], a[1]);
        for(int j = 2; j < d; j++) glca = find_lca(glca, a[j]);
        int prev = glca;
        for(int j = 0; j < d; j++){
            int lca = find_lca(prev, a[j]);
            path_aggregate(glca, a[j], 1);
            path_aggregate(glca, lca, -1);
            prev = a[j];
        }
        
    }
    dfs2(0, -1);
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<"\n";
    for(auto x : ans) cout<<x + 1<<" ";
    cout<<"\n";
}

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