Submission #547659

#	Time	Username	Problem	Language	Result	Execution time	Memory
547659		tabr	Ideal city (IOI12_city)	C++17	100 / 100	449 ms	37288 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45