제출 #1030615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030615		shiomusubi496	Simurgh (IOI17_simurgh)	C++17	100 / 100	477 ms	23996 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

constexpr ll inf = 1e18;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

class UnionFind {
    int n;
    vector<int> par, wei; // a[x] = a[r] + wei[x]

public:
    UnionFind(int n_) : n(n_), par(n_, -1), wei(n, 0) {}
    int find(int x) {
        if (par[x] < 0) return x;
        int r = find(par[x]);
        wei[x] += wei[par[x]];
        return par[x] = r;
    }
    int weight(int x) {
        find(x);
        return wei[x];
    }
    // a[x] = a[y] + w
    bool merge(int x, int y, int w) {
        w = weight(x) - w - weight(y);
        x = find(x), y = find(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y), w = -w;
        par[x] += par[y];
        par[y] = x;
        wei[y] = w;
        return true;
    }
    int diff(int x, int y) { return weight(y) - weight(x); }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -par[find(x)]; }
};

struct edge {
    int to, idx;
    bool operator==(const edge& e) const { return to == e.to && idx == e.idx; }
};

class BiConnectedComponents {
    vector<vector<edge>> g;
    vector<int> ord, low;
    vector<int> stk;
    vector<vector<int>> bcc;
    int idx;

    void dfs(int v, int p) {
        ord[v] = low[v] = idx++;
        for (auto e : g[v]) {
            if (e.to == p) continue;
            if (ord[e.to] == -1) {
                stk.push_back(e.idx);
                dfs(e.to, v);
                chmin(low[v], low[e.to]);
                if (ord[v] <= low[e.to]) {
                    vector<int> comp;
                    while (true) {
                        int f = stk.back();
                        stk.pop_back();
                        comp.push_back(f);
                        if (f == e.idx) break;
                    }
                    bcc.push_back(comp);
                }
            } else {
                chmin(low[v], ord[e.to]);
                if (ord[v] > ord[e.to]) stk.push_back(e.idx);
            }
        }
    }

public:
    BiConnectedComponents(int n) : g(n), ord(n, -1), low(n), idx(0) {}

    void add_edge(int u, int v) {
        g[u].push_back({v, idx});
        g[v].push_back({u, idx});
        ++idx;
    }

    vector<vector<int>> build() {
        idx = 0;
        rep (i, g.size()) if (ord[i] == -1) dfs(i, -1);
        return bcc;
    }
};

map<vector<int>, int> memo;

int Query(vector<int> es) {
    sort(all(es));
    if (memo.count(es)) return memo[es];
    return memo[es] = count_common_roads(es);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    if (n == 2) return {0};
    BiConnectedComponents bcc(n);
    rep (i, u.size()) bcc.add_edge(u[i], v[i]);
    auto comp = bcc.build();
    vector<int> cmpid(u.size(), -1);
    rep (i, comp.size()) for (auto e : comp[i]) cmpid[e] = i;
    vector<vector<edge>> g1(n);
    rep (i, u.size()) {
        g1[u[i]].push_back({v[i], i});
        g1[v[i]].push_back({u[i], i});
    }
    vector<int> ans;
    rep (c, comp.size()) {
        if (comp[c].size() == 1) {
            ans.push_back(comp[c][0]);
            continue;
        }
        vector<int> es;
        {
            vector<bool> seen(n, false);
            rep (i, n) {
                auto dfs = [&](auto&& self, int v) -> void {
                    seen[v] = true;
                    for (auto e : g1[v]) if (!seen[e.to] && cmpid[e.idx] != c) {
                        es.push_back(e.idx);
                        self(self, e.to);
                    }
                };
                if (!seen[i]) {
                    dfs(dfs, i);
                }
            }
        }
        vector<int> U, V;
        int n2 = 0;
        {
            vector<int> a;
            for (auto i : comp[c]) {
                a.push_back(u[i]);
                a.push_back(v[i]);
            }
            sort(all(a));
            a.erase(unique(all(a)), end(a));
            for (auto i : comp[c]) {
                U.push_back(lower_bound(all(a), u[i]) - begin(a));
                V.push_back(lower_bound(all(a), v[i]) - begin(a));
            }
            n2 = a.size();
        }
        vector<vector<edge>> g(n2);
        rep (i, U.size()) {
            g[U[i]].push_back({V[i], i});
            g[V[i]].push_back({U[i], i});
        }
        vector<int> es2;
        vector<int> dep(n2, -1), par(n2, -1), pe(n2, -1);
        {
            auto dfs = [&](auto&& self, int v, int p) -> void {
                for (auto e : g[v]) if (dep[e.to] == -1) {
                    es2.push_back(e.idx);
                    dep[e.to] = dep[v] + 1;
                    par[e.to] = v;
                    pe[e.to] = e.idx;
                    self(self, e.to, v);
                }
            };
            dep[0] = 0;
            dfs(dfs, 0, -1);
        }
        auto lca = [&](int u, int v) -> int {
            while (u != v) {
                if (dep[u] < dep[v]) swap(u, v);
                u = par[u];
            }
            return u;
        };
        UnionFind uf(comp[c].size());
        auto es_ = es;
        for (auto i : es2) es.push_back(comp[c][i]);
        int c1 = Query(es);
        rep (i, comp[c].size()) {
            if (count(all(es2), i)) continue;
            int l = lca(U[i], V[i]);
            if (dep[U[i]] < dep[V[i]]) swap(U[i], V[i]);
            int v = U[i];
            vector<int> pes;
            while (v != l) {
                pes.push_back(pe[v]);
                v = par[v];
            }
            if (pes.empty() || uf.same(pes.front(), pes.back())) continue;
            v = U[i];
            while (v != l) {
                int j = i, k = pe[v];
                if (!uf.same(j, k)) {
                    auto es2 = es;
                    es2.erase(find(all(es2), comp[c][k]));
                    es2.push_back(comp[c][j]);
                    int c2 = Query(es2);
                    uf.merge(j, k, c2 - c1);
                }
                v = par[v];
            }
        }
        int mn = 0;
        int r = pe[1];
        rep (i, comp[c].size()) if (uf.same(r, i)) chmin(mn, uf.weight(i));
        vector<bool> is_common(comp[c].size(), false);
        vector<int> used_es;
        rep (i, comp[c].size()) if (uf.same(r, i)) {
            if (uf.weight(i) != mn) {
                ans.push_back(comp[c][i]);
                is_common[i] = true;
            }
            g[U[i]].erase(find(all(g[U[i]]), edge{V[i], i}));
            g[V[i]].erase(find(all(g[V[i]]), edge{U[i], i}));
            used_es.push_back(i);
        }

        // for (auto i : comp[c]) cout << i << " "; cout << endl;
        // for (auto i : used_es) cout << i << " "; cout << endl;
        // for (auto i : is_common) cout << i << " "; cout << endl;
        // for (auto i : es_) cout << i << " "; cout << endl;

        auto ask = [&](vector<int> es) {
            UnionFind uf(n2);
            for (auto i : es) uf.merge(U[i], V[i], 0);
            int cnt = 0;
            for (int i : used_es) {
                if (uf.merge(U[i], V[i], 0)) {
                    es.push_back(i);
                    if (is_common[i]) ++cnt;
                }
            }
            rep (i, n2) assert(uf.same(0, i));
            for (auto& i : es) i = comp[c][i];
            for (auto i : es_) es.push_back(i);
            return Query(es) - cnt;
        };
        int c2 = ask({});
        rep (i, n2) {
            vector<int> es;
            for (auto e : g[i]) es.push_back(e.idx);
            int t = ask(es) - c2;
            rep (i, t) {
                int ok = 0, ng = es.size();
                while (ng - ok > 1) {
                    int mid = (ok + ng) / 2;
                    vector<int> es2;
                    rep (j, mid) es2.push_back(es[j]);
                    if (ask(es2) - c2 > i) ng = mid;
                    else ok = mid;
                }
                ans.push_back(comp[c][es[ok]]);
            }
            for (auto e : g[i]) {
                g[e.to].erase(find(all(g[e.to]), edge{i, e.idx}));
            }
        }
    }
    sort(all(ans));
    ans.erase(unique(all(ans)), ans.end());
    return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30