oj.uz

Submission #412678

# Submission time Handle Problem Language Result Execution time Memory
412678 2021-05-27T10:28:09 Z KoD Ideal city (IOI12_city) C++17
100 / 100
 130 ms 11332 KB 
#include <bits/stdc++.h>

constexpr int MOD = 1000000000;

template <class T>
using Vec = std::vector<T>;

struct UnionFind {
    Vec<int> par;
    std::stack<std::pair<int, int>> stack;
    UnionFind(const int n): par(n, -1), stack() {}
    int find(int u) const {
        while (par[u] >= 0) {
            u = par[u];
        }
        return u;
    }
    int size(const int u) const {
        return -par[find(u)];
    }
    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        stack.emplace(x, par[x]);
        stack.emplace(y, par[y]);
        par[x] += par[y];
        par[y] = x;
        return 1;
    }
    void roll(int size) {
        size *= 2;
        while (size--) {
            const auto [i, v] = stack.top();
            stack.pop();
            par[i] = v;
        }
    }
};

int solve(int N, int *X, int *Y) {
    std::map<int, Vec<std::pair<int, int>>> map;
    for (int i = 0; i < N; ++i) {
        map[X[i]].emplace_back(Y[i], i);
    }
    for (auto& [x, v]: map) {
        std::sort(v.begin(), v.end());
    }
    UnionFind left(N), right(N);
    std::stack<int> roll;
    const auto try_find = [&](const int x, const int y) {
        const auto& vec = map[x];
        auto itr = std::lower_bound(vec.cbegin(), vec.cend(), std::make_pair(y, 0));
        if (itr == vec.cend() or itr -> first != y) {
            return -1;
        }
        return itr -> second;
    };
    for (auto itr = map.rbegin(); itr != map.rend(); ++itr) {
        const auto& [x, v] = *itr;
        int sum = 0;
        for (int i = 1; i < (int) v.size(); ++i) {
            if (v[i - 1].first + 1 == v[i].first) {
                sum += right.merge(v[i - 1].second, v[i].second);
            }
        }
        for (const auto [y, u]: v) {
            const auto k = try_find(x + 1, y);
            if (k != -1) {
                sum += right.merge(u, k);
            }
        }
        roll.push(sum);
    }
    Vec<Vec<int>> graph(N);
    Vec<int> size(N);
    int ret = 0;
    for (const auto& [x, v]: map) {
        right.roll(roll.top());
        roll.pop();
        {
            for (int i = 1; i < (int) v.size(); ++i) {
                if (v[i - 1].first + 1 == v[i].first) {
                    left.merge(v[i - 1].second, v[i].second);
                }
            }
            for (const auto [y, u]: v) {
                const auto k = try_find(x - 1, y);
                if (k != -1) {
                    left.merge(u, k);
                }
            }
        }
        Vec<std::pair<int, int>> edge;
        {
            int last = -1;
            for (int i = 0; i < (int) v.size(); ++i) {
                const auto k = try_find(x + 1, v[i].first);
                if (k != -1) {
                    if (last + 1 != v[i].first) {
                        edge.emplace_back(left.find(v[i].second), right.find(k));
                    }
                    last = v[i].first;
                }
            }
        }
        if (edge.empty()) {
            continue;
        }
        for (const auto [x, y]: edge) {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        Vec<int> coeff;
        auto dfs = [&](auto&& dfs, const int u, const int p) -> void {
            size[u] = (X[u] <= x ? left : right).size(u);
            for (const auto v: graph[u]) {
                if (v != p) {
                    dfs(dfs, v, u);
                    size[u] += size[v];
                }
            }
            coeff.push_back(size[u]);
        };
        const auto root = edge.front().first;
        dfs(dfs, root, -1);
        for (const auto x: coeff) {
            ret += (long long) x * (coeff.back() - x) % MOD;
            ret %= MOD;
        }
        for (const auto [x, y]: edge) {
            graph[x].clear();
            graph[y].clear();
        }
    }
    return ret;
}

int DistanceSum(int N, int *X, int *Y) {
    return (solve(N, X, Y) + solve(N, Y, X)) % MOD;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 440 KB Output is correct
7 Correct 3 ms 392 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1880 KB Output is correct
2 Correct 19 ms 1996 KB Output is correct
3 Correct 49 ms 4360 KB Output is correct
4 Correct 50 ms 4492 KB Output is correct
5 Correct 103 ms 8440 KB Output is correct
6 Correct 102 ms 8516 KB Output is correct
7 Correct 106 ms 8584 KB Output is correct
8 Correct 102 ms 8436 KB Output is correct
9 Correct 110 ms 8352 KB Output is correct
10 Correct 123 ms 11332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1908 KB Output is correct
2 Correct 24 ms 2036 KB Output is correct
3 Correct 63 ms 4664 KB Output is correct
4 Correct 60 ms 4528 KB Output is correct
5 Correct 128 ms 8988 KB Output is correct
6 Correct 115 ms 8500 KB Output is correct
7 Correct 130 ms 8872 KB Output is correct
8 Correct 117 ms 8604 KB Output is correct
9 Correct 107 ms 8388 KB Output is correct
10 Correct 113 ms 8412 KB Output is correct