oj.uz

Submission #157820

# Submission time Handle Problem Language Result Execution time Memory
157820 2019-10-13T07:02:03 Z gs13105 Ideal city (IOI12_city) C++17
100 / 100
 598 ms 19416 KB 
#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.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 6232 KB Output is correct
2 Correct 86 ms 6196 KB Output is correct
3 Correct 199 ms 10520 KB Output is correct
4 Correct 196 ms 10224 KB Output is correct
5 Correct 516 ms 18636 KB Output is correct
6 Correct 547 ms 18016 KB Output is correct
7 Correct 561 ms 18016 KB Output is correct
8 Correct 598 ms 18880 KB Output is correct
9 Correct 548 ms 17528 KB Output is correct
10 Correct 596 ms 19416 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5744 KB Output is correct
2 Correct 76 ms 6012 KB Output is correct
3 Correct 206 ms 9616 KB Output is correct
4 Correct 222 ms 10540 KB Output is correct
5 Correct 541 ms 16200 KB Output is correct
6 Correct 525 ms 17964 KB Output is correct
7 Correct 521 ms 16200 KB Output is correct
8 Correct 526 ms 17728 KB Output is correct
9 Correct 515 ms 17644 KB Output is correct
10 Correct 545 ms 17772 KB Output is correct