Submission #490904

#	Time	Username	Problem	Language	Result	Execution time	Memory
490904		MohammadAghil	Railway (BOI17_railway)	C++14	100 / 100	104 ms	27608 KiB

railway

#include <bits/stdc++.h> 
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
using namespace std; 
typedef long long ll; 
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 

const ll mod = 1e9 + 7, maxn = 2e5 + 2, lg = 20, inf = 1e9 + 5;

vector<pp> adj[maxn];
vector<int> ans;
int par[maxn][lg], st[maxn], t, h[maxn], val[maxn], k;

void dfs(int r, int p){
    par[r][0] = p;
    rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
    st[r] = t++;
    for(pp c: adj[r]) if(c.ff != p){
        h[c.ff] = h[r] + 1;
        dfs(c.ff, r);
    }
}

int lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    rep(i,0,lg) if((h[v] - h[u])>>i&1) v = par[v][i];
    if(v == u) return u;
    per(i,lg-1,0) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

int dfs2(int r, int p){
    int cr = 0;
    for(pp c: adj[r]) if(c.ff != p){
        int t = dfs2(c.ff, r);
        if(t >= k << 1) ans.pb(c.ss);
        cr += t;
    }
    cr += val[r];
    return cr;
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);
    int n, m; cin >> n >> m >> k;
    rep(i,0,n-1){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    } dfs(0, 0);
    rep(i,0,m){
        int s; cin >> s;
        vector<int> nd(s);
        rep(i,0,s){
            cin >> nd[i]; nd[i]--;
        }
        sort(all(nd), [&](int a, int b){
            return st[a] < st[b];
        });
        rep(i,0,s){
            int u = nd[i], v = nd[(i + 1)%s];
            if(h[u] > h[v]) swap(u, v);
            int l = lca(u, v);
            if(l == u) val[l]--, val[v]++;
            else val[l] -= 2, val[u]++, val[v]++;
        }
    } dfs2(0, 0);
    sort(all(ans));
    cout << sz(ans) << '\n';
    for(int c: ans) cout << ++c << ' ';
    return 0;
}

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