oj.uz

Submission #102374

# Submission time Handle Problem Language Result Execution time Memory
102374 2019-03-24T14:41:02 Z naoai Ideal city (IOI12_city) C++14
100 / 100
 720 ms 15416 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
const int mod = 1e9;
const int nmax = 1e5;

i64 sum;
int n;
int sz[nmax + 1], comp[nmax + 1];
bool viz[nmax + 1];
vector<int> g[nmax + 1];

map<pair<int, int>, int> mp;

void dfs (int nod, pair<int, int> pos, int ind) { // componentele sunt secventele consec pe ac coloana
    if (viz[nod] == 1)
        return ;

    ++ sz[ind];
    viz[nod] = 1;
    comp[nod] = ind;

    -- pos.first;
    if (mp.find(pos) != mp.end()) {
        dfs(mp[pos], pos, ind);
    }

    pos.first += 2;
    if (mp.find(pos) != mp.end()) {
        dfs(mp[pos], pos, ind);
    }
}

void calc (int nod, int t) {
    for (auto i : g[nod]) {
        if (i != t) {
            calc(i, nod);

            sz[nod] += sz[i];
        }
    }

    sum = (sum + 1LL * sz[nod] * (n - sz[nod])) % mod;
}

int solve (int N, int *X, int *Y) {
    for (int i = 0; i < N; ++ i)
        mp[{X[i], Y[i]}] = i;

    int nrc = 0;
    for (int i = 0; i < N; ++ i) {
        if (viz[i] == 0) {
            dfs(i, {X[i], Y[i]}, ++ nrc);
        }
    }

    n = N;

    for (int i = 0; i < N; ++ i) {
        int y = Y[i] + 1;
        if (mp.find({X[i], y}) != mp.end()) {
            int u = comp[mp[{X[i], y}]];

            g[comp[i]].push_back(u);
            g[u].push_back(comp[i]);
        }
    }

    for (int i = 1; i <= nrc; ++ i) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }

    sum = 0;
    calc(1, 0);

    memset(sz, 0, sizeof(sz));
    memset(viz, 0, sizeof(viz));
    mp.clear();
    for (int i = 1; i <= nrc; ++ i) {
        g[i].clear();
    }

    return sum;
}

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

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5124 KB Output is correct
2 Correct 71 ms 5320 KB Output is correct
3 Correct 214 ms 8144 KB Output is correct
4 Correct 261 ms 8532 KB Output is correct
5 Correct 607 ms 13432 KB Output is correct
6 Correct 630 ms 13816 KB Output is correct
7 Correct 565 ms 13284 KB Output is correct
8 Correct 631 ms 12848 KB Output is correct
9 Correct 678 ms 13548 KB Output is correct
10 Correct 622 ms 15416 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5220 KB Output is correct
2 Correct 72 ms 5256 KB Output is correct
3 Correct 267 ms 8412 KB Output is correct
4 Correct 238 ms 8312 KB Output is correct
5 Correct 625 ms 13304 KB Output is correct
6 Correct 583 ms 13432 KB Output is correct
7 Correct 639 ms 13356 KB Output is correct
8 Correct 712 ms 13432 KB Output is correct
9 Correct 720 ms 13072 KB Output is correct
10 Correct 687 ms 13176 KB Output is correct