oj.uz

Submission #1030501

# Submission time Handle Problem Language Result Execution time Memory
1030501 2024-07-22T06:06:39 Z shiomusubi496 Simurgh (IOI17_simurgh) C++17
51 / 100
 111 ms 10028 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 344 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 344 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 600 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 600 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 1 ms 608 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 348 KB correct
23 Correct 1 ms 436 KB correct
24 Correct 1 ms 344 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 1 ms 464 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 348 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 344 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 600 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 600 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 1 ms 608 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 348 KB correct
23 Correct 1 ms 436 KB correct
24 Correct 1 ms 344 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 1 ms 464 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 348 KB correct
34 Correct 110 ms 3464 KB correct
35 Correct 109 ms 3560 KB correct
36 Correct 73 ms 2936 KB correct
37 Correct 5 ms 600 KB correct
38 Correct 110 ms 3588 KB correct
39 Correct 102 ms 3412 KB correct
40 Correct 81 ms 3112 KB correct
41 Correct 108 ms 3684 KB correct
42 Correct 111 ms 3468 KB correct
43 Correct 52 ms 2304 KB correct
44 Correct 45 ms 1628 KB correct
45 Correct 48 ms 1816 KB correct
46 Correct 37 ms 1368 KB correct
47 Correct 16 ms 856 KB correct
48 Correct 2 ms 348 KB correct
49 Correct 5 ms 604 KB correct
50 Correct 16 ms 1168 KB correct
51 Correct 57 ms 2028 KB correct
52 Correct 42 ms 1884 KB correct
53 Correct 40 ms 1800 KB correct
54 Correct 57 ms 2640 KB correct
55 Correct 50 ms 2024 KB correct
56 Correct 50 ms 2024 KB correct
57 Correct 50 ms 2020 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 0 ms 344 KB correct
3 Incorrect 95 ms 10028 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 344 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 600 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 600 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 1 ms 608 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 348 KB correct
23 Correct 1 ms 436 KB correct
24 Correct 1 ms 344 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 1 ms 464 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 348 KB correct
34 Correct 110 ms 3464 KB correct
35 Correct 109 ms 3560 KB correct
36 Correct 73 ms 2936 KB correct
37 Correct 5 ms 600 KB correct
38 Correct 110 ms 3588 KB correct
39 Correct 102 ms 3412 KB correct
40 Correct 81 ms 3112 KB correct
41 Correct 108 ms 3684 KB correct
42 Correct 111 ms 3468 KB correct
43 Correct 52 ms 2304 KB correct
44 Correct 45 ms 1628 KB correct
45 Correct 48 ms 1816 KB correct
46 Correct 37 ms 1368 KB correct
47 Correct 16 ms 856 KB correct
48 Correct 2 ms 348 KB correct
49 Correct 5 ms 604 KB correct
50 Correct 16 ms 1168 KB correct
51 Correct 57 ms 2028 KB correct
52 Correct 42 ms 1884 KB correct
53 Correct 40 ms 1800 KB correct
54 Correct 57 ms 2640 KB correct
55 Correct 50 ms 2024 KB correct
56 Correct 50 ms 2024 KB correct
57 Correct 50 ms 2020 KB correct
58 Correct 0 ms 344 KB correct
59 Correct 0 ms 344 KB correct
60 Incorrect 95 ms 10028 KB WA in grader: NO
61 Halted 0 ms 0 KB -