Submission #498549

#	Time	Username	Problem	Language	Result	Execution time	Memory
498549		MohamedFaresNebili	Railway (BOI17_railway)	C++14	0 / 100	164 ms	39708 KiB

railway

#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()

        ll n, m, k; vector<ll> adj[200005];
        ll dep[200005], par[200005][20], tin[200005];
        ll heavy[200005], top[200005], sz[200005];
        ll st[200005], lazy[200005], timer;

        void prop(ll v, ll l, ll r) {
            if(l == r || lazy[v] == 0) return;
            lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];
            ll md = (l + r) / 2;
            ll a = md - l + 1, b = r - md;
            st[v * 2] += lazy[v] * a, st[v * 2 + 1] += lazy[v] * b;
            lazy[v] = 0;
        }
        void update(ll v, ll l, ll r, ll lo, ll hi) {
            prop(v, l, r);
            if(l > hi || r < lo) return;
            if(l >= lo && r <= hi) {
                lazy[v]++; st[v] += (r - l + 1);
                prop(v, l, r); return;
            }
            update(v * 2, l, (l + r)/ 2, lo, hi);
            update(v * 2 + 1, (l + r)/2 + 1, r, lo, hi);
            st[v] = st[v * 2] + st[v * 2 + 1];
        }
        ll query(ll v, ll l, ll r, ll pos) {
            prop(v, l, r);
            if(l == r) return st[v];
            ll md = (l + r) / 2;
            if(pos <= md) return query(v * 2, l, md, pos);
            else return query(v * 2 + 1, md + 1, r, pos);
        }
        void upd(ll a, ll b) {
            while(top[a] != top[b]) {
                if(dep[top[a]] < dep[top[b]]) swap(a, b);
                update(1, 0, n - 1, tin[top[a]], tin[a]);
                a = par[top[a]][0];
            }
            if(dep[a] > dep[b]) swap(a, b);
            update(1, 0, n - 1, tin[a], tin[b]);
        }
        ll dfs(ll v, ll p) {
            dep[v] = dep[p] + 1, par[v][0] = p, sz[v] = 1;
            for(auto u : adj[v]) {
                if(u == p) continue;
                sz[v] += dfs(u, v);
            }
            return sz[v];
        }
        void HLD(ll v, ll p, ll tp) {
            top[v] = tp, tin[v] = timer++; heavy[v] = -1; ll curr = 0;
            for(auto u : adj[v]) {
                if(u == p) continue;
                if(sz[u] > curr) {
                    curr = sz[u]; heavy[v] = u;
                }
            }
            if(heavy[v] == -1) return;
            HLD(heavy[v], v, tp);
            for(auto u : adj[v]) {
                if(u == p || u == heavy[v]) continue;
                HLD(u, v, u);
            }
        }
        ll jump(ll u, ll v) {
            if(dep[u] < dep[v]) swap(u, v);
            ll f = dep[u] - dep[v];
            for(ll l = 0; l < 20; l++)
                if(f & (1 << l))
                    u = par[u][l];
            if(u == v) return u;
            for(ll l = 20 - 1; l >= 0; l--)
                if(par[u][l] != par[v][l])
                    u = par[u][l], v = par[v][l];
            return par[u][0];
        }
        ll lift(ll u, ll f) {
            for(ll l = 0; l < 20; l++)
                if(f & (1 << l))
                    u = par[u][l];
            return u;
        }

        int32_t main()
        {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m >> k; vector<ii> edges;
            for(ll l = 0; l < n - 1; l++) {
                ll u, v; cin >> u >> v; u--, v--;
                adj[u].pb(v); adj[v].pb(u);
                edges.push_back({u, v});
            }
            dep[0] = -1; dfs(0, 0); HLD(0, 0, 0);
            for(ll i = 1; i < 20; i++)
                for(ll l = 0; l < n; l++)
                    par[l][i] = par[par[l][i - 1]][i - 1];
            while(m--) {
                ll s; cin >> s;
                if(s == 2) {
                    ll u, v; cin >> u >> v; u--; v--;
                    ll lca = jump(u, v);
                    if(dep[u] < dep[v]) swap(u, v);
                    upd(lift(u, dep[u] - dep[lca] - 1), u);
                    if(v != lca) upd(lift(v, dep[v] - dep[lca] - 1), v);
                }
                else {
                    for(ll l = 0; l < s; l++) {
                        ll a; cin >> a; a--;
                    }
                }
            }
            vector<ll> res; ll curr = 0;
            for(ll l = 0; l < n - 1; l++) {
                ll u = edges[l].ff, v = edges[l].ss;
                if(dep[u] < dep[v]) swap(u, v);
                ll a = query(1, 0, n - 1, tin[u]);
                if(a >= k) res.pb(l + 1), curr++;
            }
            cout << curr << "\n";
            for(auto u : res) cout << u << " ";
            return 0;
        }

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