Submission #157820

#	Time	Username	Problem	Language	Result	Execution time	Memory
157820		gs13105	Ideal city (IOI12_city)	C++17	100 / 100	598 ms	19416 KiB

city

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000000;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int up[100010];
int us[100010];
int root(int x)
{
    return x == up[x] ? x : (up[x] = root(up[x]));
}
bool merge(int x, int y)
{
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;
    up[x] = y;
    us[y] += us[x];
    us[x] = 0;
    return 1;
}

int N;
int *X, *Y;
vector<int> edg[100010];
int siz[100010];

int f(int x, int p)
{
    int r = 0;

    siz[x] = us[x];
    for(int y : edg[x])
    {
        if(y == p)
            continue;

        r = (r + f(y, x)) % mod;
        siz[x] += siz[y];
    }

    for(int y : edg[x])
    {
        if(y == p)
            continue;

        r = (r + 1LL * siz[y] * (N - siz[y])) % mod;
    }

    return r;
}

int solve()
{
    memset(siz, 0, sizeof siz);
    for(int i = 0; i < N; i++)
    {
        up[i] = i;
        us[i] = 1;
        edg[i].clear();
    }

    map<pair<int, int>, int> m;
    for(int i = 0; i < N; i++)
        m[{ X[i], Y[i] }] = i;

    vector<pair<int, int>> tmp;
    for(int i = 0; i < N; i++)
    {
        for(int d = 0; d < 4; d++)
        {
            int nx = X[i] + dx[d];
            int ny = Y[i] + dy[d];
            auto it = m.find({ nx, ny });
            if(it != m.end())
            {
                if(d % 2 == 0)
                    merge(i, it->second);
                else
                    tmp.push_back({ i, it->second });
            }
        }
    }

    for(auto p : tmp)
    {
        int x, y;
        tie(x, y) = p;

        x = root(x);
        y = root(y);
        assert(x != y);

        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    for(int i = 0; i < N; i++)
    {
        sort(edg[i].begin(), edg[i].end());
        edg[i].erase(unique(edg[i].begin(), edg[i].end()), edg[i].end());
    }

    return f(root(1), -1);
}

int DistanceSum(int AN, int *AX, int *AY)
{
    N = AN;
    X = AX;
    Y = AY;

    int ans1 = solve();

    for(int i = 0; i < N; i++)
        swap(X[i], Y[i]);

    int ans2 = solve();

    return (ans1 + ans2) % mod;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45