Submission #441670

#	Time	Username	Problem	Language	Result	Execution time	Memory
441670		Mahfel	Railway (BOI17_railway)	C++17	23 / 100	1094 ms	35908 KiB

railway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 1e5 + 20 , LOG = 19;
vector<int> adj[MXN];
vector<int> euler;
map<pair<int,int>,int> idx;
int st_time[MXN] , sz[MXN] , p[LOG][MXN] , h[MXN];
int d[MXN] , ans[MXN] , sm[MXN];
int n,m,k;
 
struct seg_tree {
    int size;
    vector<int> v;
    seg_tree() {
        size = 1;
        while(size < n) size <<= 1;
        v.assign(2*size , 0);
    }
 
    void add(int x , int lx , int rx , int i , int k) {
        if(rx-lx == 1) {
            v[x] += k; return;
        }
        int m = (lx+rx)/2;
        if(i < m) {
            add(2*x+1 , lx , m , i , k);
        } else {
            add(2*x+2 , m , rx , i , k);
        }
        v[x] = v[2*x+1] + v[2*x+2];
    }
    void add(int i , int k) {
        add(0 , 0 , size , i , k);
    }
 
    int sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            return v[x];
        }
        if(lx >= r || rx <= l) {
            return 0;
        }
        int m = (lx+rx)/2;
        return sum(2*x+1 , lx , m , l , r) + sum(2*x+2 , m , rx , l , r);
    }
    int sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
};
 
struct fenwick {
    vector<int> v;
    fenwick() {
        v.assign(n , 0);
    }
 
    void add(int i , int k) {
        for(; i < n ; i = (i|(i+1))) {
            v[i] += k;
        }
    }
 
    int sum(int x) {
        if(x < 0) return 0;
        int ans = 0;
        for(; x >= 0 ; x = (x&(x+1))-1) {
            ans += v[x];
        }
        return ans;
    }
    int sum(int l , int r) {
        return sum(r)-sum(l-1);
    }
};
 
void DFS(int v , int dad) {
    euler.push_back(v); st_time[v] = euler.size()-1;
    sz[v] = 1;
    p[0][v] = (dad == -1 ? v : dad);
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    for(auto u : adj[v]) {
        if(u == dad) continue;
        DFS(u , v);
        sz[v] += sz[u];
    }
}
 
void final_DFS(int v , int dad) {
    int res = d[v];
    for(auto u : adj[v]) {
        if(u == dad) continue;
        final_DFS(u , v);
        res += sm[u];
    }
    sm[v] = res;
    if(dad != -1) ans[idx[{v , dad}]] = res;
}
 
void build_LCA() {
    for(int i = 1 ; i < LOG ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }
}
int kth_anc(int k , int v) {
    while(k > 0) {
        int x = __builtin_ctz(k);
        v = p[x][v];
        k -= (1 << x);
    }
    return v;
}
int LCA(int v , int u) {
    if(h[v] > h[u]) swap(v,u);
    u = kth_anc(h[u]-h[v] , u);
    if(u == v) return v;
    for(int i = LOG-1 ; i >= 0 ; i--) {
        if(p[i][v] != p[i][u]) {
            v = p[i][v]; u = p[i][u];
        }
    }
    return p[0][v];
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m >> k;
    for(int i = 1 ; i < n ; i++) {
        int v,u; cin >> v >> u;
        adj[v].push_back(u); adj[u].push_back(v);
        idx[{v , u}] = i; idx[{u , v}] = i;
    }
    DFS(1 , -1);
    build_LCA();
 
    for(int q = 0 ; q < m ; q++) {
 
        fenwick fen;
        int s; cin >> s;
        int v,u; cin >> v >> u;
        int lca = LCA(v , u);
        d[v]++; d[u]++; d[lca] -= 2;
        fen.add(st_time[v] , 1); fen.add(st_time[u] , 1);
        v = lca;
        for(int i = 2 ; i < s ; i++) {
            int u; cin >> u;
            lca = LCA(v , u);
            if(lca != v) {
                d[u]++; d[v]++; d[lca] -= 2;
                fen.add(st_time[u] , 1);
            } else {
                if(fen.sum(st_time[u] , st_time[u]+sz[u]-1) > 0) continue;
                int _u = u;
                for(int i = LOG-1 ; i >= 0 ; i--) {
                    int par = p[i][_u];
                    if(par != 1 && fen.sum(st_time[par] , st_time[par]+sz[par]-1) <= 0) {
                        _u = par;
                    }
                }
                _u = p[0][_u];
                d[u]++; d[_u]--;
                fen.add(st_time[u] , 1);
            }
            v = lca;
        }
    }
 
    final_DFS(1 , -1);
    vector<int> res;
    for(int i = 1 ; i < n ; i++) {
        if(ans[i] >= k) res.push_back(i);
    }
    cout << res.size() << "\n";
    for(auto u : res) {
        cout << u << " ";
    }
    cout << "\n";
 
}

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