Submission #924079

#	Time	Username	Problem	Language	Result	Execution time	Memory
924079		Perl32	Railway (BOI17_railway)	C++14	100 / 100	101 ms	22724 KiB

railway

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct HLD {
    vector<int> par, siz, head, tin;
    vector<vector<int>> g;

    int dfs1(int u) {
        for (int &to : g[u]) {
            if (to == par[u]) {
                continue;
            }
            par[to] = u;
            siz[u] += dfs1(to);
            if (siz[to] > siz[g[u][0]] || g[u][0] == par[u]) swap(to, g[u][0]);
        }
        return siz[u];
    }

    void dfs2(int u, int &timer) {
        tin[u] = timer++;
        for (int to : g[u]) {
            if (to == par[u]) {
                continue;
            }
            head[to] = (timer == tin[u] + 1 ? head[u] : to);
            dfs2(to, timer);
        }
    }

    HLD(vector<vector<int>> &g, int r = 0) : par(g.size(), -1), siz(g.size(), 1), head(g.size(), r), tin(g.size()), g(g) {
        dfs1(r);
        int timer = 0;
        dfs2(r, timer);
    }

    vector<pair<int, int>> path(int a, int b) {
        vector<pair<int, int>> res;
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) {
                res.emplace_back(tin[a] + 1, tin[b] + 1);
                return res;
            }
            res.emplace_back(tin[head[b]], tin[b] + 1);
        }
    }

    int lca(int a, int b) {
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) return a;
        }
    }
};

template<typename T>
class Fenwick { //0-indexed, [l, r)
 public:
    vector<T> t;
    int n;

    Fenwick() = default;
    explicit Fenwick(int n) : t(n + 1), n(n) {}

    T get(int x) {
        T ans = 0;
        for (x; x > 0; x -= x & -x) {
            ans += t[x];
        }
        return ans;
    }

    T get(int l, int r) {
        return get(r) - get(l);
    }

    void upd(int x, T v) {
        for (++x; x <= n; x += x & -x) {
            t[x] += v;
        }
    }

    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i > 0; i >>= 1) {
            if (x + i <= n && t[x + i] < k) {
                k -= t[x += i];
            }
        }
        return x;
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> g(n);
    vector<pair<int, int>> e;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        e.emplace_back(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    HLD tr(g);
    vector<int> par(n);
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v] = e[i];
        if (tr.tin[u] > tr.tin[v]) swap(u, v);
        par[tr.tin[v]] = i;
    }
    Fenwick<int> bit(n + 1);
    for (int i = 0; i < m; ++i) {
        int K;
        cin >> K;
        vector<int> v(K);
        for (int j = 0; j < K; ++j) {
            cin >> v[j];
            --v[j];
        }
        int lca = v[0];
        for (int j = 1; j < K; ++j) {
            lca = tr.lca(lca, v[j]);
        }
        vector<pair<int, int>> ev;
        for (auto x : v) {
            for (auto [lx, rx] : tr.path(lca, x)) {
                if (lx == rx) continue;
                ev.emplace_back(lx, -1);
                ev.emplace_back(rx, 1);
            }
        }
        sort(ev.begin(), ev.end());
        vector<pair<int, int>> add;
        int last = 0, c = 0;
        for (auto [x, t] : ev) {
            if (t == 1 && c == 1) {
                bit.upd(last, 1);
                bit.upd(x, -1);
            }
            c -= t;
            if (t == -1 && c == 1) {
                last = x;
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (bit.get(i + 1) >= k) {
            ans.push_back(par[i]);
        }
    }
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (auto i : ans) {
        cout << i + 1 << ' ';
    }
}

/*

 */

Compilation message (stderr)

railway.cpp: In function 'int main(int32_t, char**)':
railway.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |         auto [u, v] = e[i];
      |              ^
railway.cpp:142:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |             for (auto [lx, rx] : tr.path(lca, x)) {
      |                       ^
railway.cpp:151:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |         for (auto [x, t] : ev) {
      |                   ^
railway.cpp: In instantiation of 'T Fenwick<T>::get(int) [with T = int]':
railway.cpp:164:26:   required from here
railway.cpp:77:14: warning: statement has no effect [-Wunused-value]
   77 |         for (x; x > 0; x -= x & -x) {
      |              ^

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