oj.uz

답안 #547659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547659 2022-04-11T08:32:02 Z tabr 이상적인 도시 (IOI12_city) C++17
100 / 100
 449 ms 37288 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

int DistanceSum(int n, int x[], int y[]) {
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        mp[make_pair(x[i], y[i])] = i;
    }
    vector<vector<int>> g(n);
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    for (int i = 0; i < n; i++) {
        for (int dir = 0; dir < 4; dir++) {
            int nx = x[i] + dx[dir];
            int ny = y[i] + dy[dir];
            if (mp.count(make_pair(nx, ny))) {
                g[i].emplace_back(mp[make_pair(nx, ny)]);
            }
        }
    }
    vector<int> rx, ry;
    map<pair<int, int>, int> sx, sy;
    for (int z = 0; z < 2; z++) {
        dsu uf(n);
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                if (x[i] == x[j]) {
                    uf.unite(i, j);
                }
            }
        }
        vector<vector<int>> f(n);
        vector<int> r(n);
        for (int i = 0; i < n; i++) {
            r[i] = uf.get(i);
            if (i != r[i]) {
                f[i].emplace_back(r[i]);
                f[r[i]].emplace_back(i);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                if (y[i] == y[j] && uf.unite(i, j)) {
                    f[r[i]].emplace_back(r[j]);
                    f[r[j]].emplace_back(r[i]);
                }
            }
        }
        map<pair<int, int>, int> s;
        vector<int> sz(n);
        function<void(int, int)> Dfs = [&](int v, int p) {
            sz[v] = 1;
            for (int to : f[v]) {
                if (to == p) {
                    continue;
                }
                Dfs(to, v);
                sz[v] += sz[to];
            }
            if (p != -1 && r[v] == v && r[p] == p) {
                s[make_pair(p, v)] = (n - sz[v]) - sz[v];
                s[make_pair(v, p)] = sz[v] - (n - sz[v]);
            }
        };
        Dfs(0, -1);
        rx = r;
        sx = s;
        swap(x, y);
        swap(rx, ry);
        swap(sx, sy);
    }
    long long now0 = 0;
    {
        vector<int> d(n, -1);
        queue<int> que;
        d[0] = 0;
        que.emplace(0);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int to : g[v]) {
                if (d[to] == -1) {
                    d[to] = d[v] + 1;
                    que.emplace(to);
                }
            }
        }
        now0 = accumulate(d.begin(), d.end(), 0LL);
    }
    long long res = 0;
    vector<int> was(n);
    function<void(int, long long)> Dfs = [&](int v, long long now) {
        debug(v, now);
        res += now;
        was[v] = 1;
        for (int to : g[v]) {
            if (was[to]) {
                continue;
            }
            long long nxt = now;
            if (x[v] != x[to]) {
                nxt += sx[make_pair(rx[v], rx[to])];
            } else {
                nxt += sy[make_pair(ry[v], ry[to])];
            }
            Dfs(to, nxt);
        }
    };
    Dfs(0, now0);
    return (int) (res / 2 % (long long) 1e9);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 11;
    int x[] = {2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5};
    int y[] = {5, 6, 3, 6, 3, 4, 5, 6, 3, 4, 6};
    cout << DistanceSum(n, x, y) << '\n';
    return 0;
}
#endif

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 5 ms 952 KB Output is correct
7 Correct 5 ms 1084 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 6 ms 920 KB Output is correct
10 Correct 5 ms 852 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 6920 KB Output is correct
2 Correct 46 ms 7036 KB Output is correct
3 Correct 125 ms 16700 KB Output is correct
4 Correct 142 ms 16564 KB Output is correct
5 Correct 303 ms 33156 KB Output is correct
6 Correct 315 ms 33220 KB Output is correct
7 Correct 331 ms 32776 KB Output is correct
8 Correct 313 ms 33180 KB Output is correct
9 Correct 341 ms 33184 KB Output is correct
10 Correct 312 ms 36116 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 7692 KB Output is correct
2 Correct 50 ms 6976 KB Output is correct
3 Correct 206 ms 18568 KB Output is correct
4 Correct 166 ms 16472 KB Output is correct
5 Correct 418 ms 36796 KB Output is correct
6 Correct 367 ms 29896 KB Output is correct
7 Correct 449 ms 37288 KB Output is correct
8 Correct 364 ms 28968 KB Output is correct
9 Correct 354 ms 28836 KB Output is correct
10 Correct 379 ms 26500 KB Output is correct