Submission #498883

#	Time	Username	Problem	Language	Result	Execution time	Memory
498883		MohamedFaresNebili	Railway (BOI17_railway)	C++14	100 / 100	450 ms	40960 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[2 * 100005];
        ll dep[2 * 100005], par[2 * 100005][20], tin[2 * 100005];
        ll heavy[2 * 100005], top[2 * 100005], sz[2 * 100005];
        ll st[6 * 100005], lazy[6 * 100005], 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 k = dep[u] - dep[v];
            for(ll l = 0; l < 20; l++)
                if(k & (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 k) {
            for(ll l = 0; l < 20; l++)
                if(k & (1 << l))
                    u = par[u][l];
            return u;
        }
        bool comp(int u, int v) { return tin[u] < tin[v]; }

        int32_t main()
        {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m >> k; vector<ii> edges; bool subtask2 = 1;
            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});
            }
            for(ll l = 0; l < n; l++)
                subtask2 &= ((ll)adj[l].size() <= 2);
            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; vector<int> arr(s);
                for(int l = 0; l < s; l++) { cin >> arr[l]; arr[l]--; }
                sort(all(arr), comp); arr.pb(arr[0]);
                for(int l = 0; l < s; l++) {
                    int u = arr[l], v = arr[l + 1];
                    int lca = jump(u, v);
                    if(dep[u] < dep[v]) swap(u, v);
                    upd(u, lift(u, dep[u] - dep[lca] - 1));
                    if(v != lca) upd(v, lift(v, dep[v] - dep[lca] - 1));
                }
            }
            vector<ll> res;
            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 >= 2 * k) res.pb(l + 1);
            }
            cout << (ll)res.size() << "\n";
            for(auto u : res) cout << u << " ";
            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