Submission #1030501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030501		shiomusubi496	Simurgh (IOI17_simurgh)	C++17	51 / 100	111 ms	10028 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; };

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;
    }
};

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()) {
        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());
        for (auto i : es2) es.push_back(comp[c][i]);
        int c1 = count_common_roads(es);
        rep (i, U.size()) {
            if (count(all(es), comp[c][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];
            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 = count_common_roads(es2);
                    uf.merge(j, k, c2 - c1);
                }
                v = par[v];
            }
        }
        int mx = 0;
        rep (i, comp[c].size()) chmax(mx, uf.weight(i));
        rep (i, comp[c].size()) if (uf.weight(i) == mx) ans.push_back(comp[c][i]);
    }
    return ans;
}

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