oj.uz

Submission #161660

# Submission time Handle Problem Language Result Execution time Memory
161660 2019-11-03T13:29:25 Z dolphingarlic Ideal city (IOI12_city) C++14
100 / 100
 234 ms 38008 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define x first
#define y second
typedef long long ll;
using namespace std;

const ll MOD = 1e9;

int N;
pair<int, int> srtd[2][100001];
set<int> graphs[2][100001];
ll num_blocks[2][100001], dp[2][100001], ans = 0;
int x = 0, y = 0;
map<pair<int, int>, int> x_cmp, y_cmp;

void dfs1(int dir, int node, int parent = 0) {
    for (int i : graphs[dir][node]) if (i != parent) {
        dfs1(dir, i, node);
        dp[dir][node] += dp[dir][i];
        ans = (ans + (N - dp[dir][i]) * dp[dir][i]) % MOD;
    }
}

int DistanceSum(int N, int *X, int *Y) {
    ::N = N;
    FOR(i, 0, N) {
        srtd[0][i] = {X[i], Y[i]};
        srtd[1][i] = {Y[i], X[i]};
    }
    sort(srtd[0], srtd[0] + N);
    sort(srtd[1], srtd[1] + N);

    FOR(i, 0, N) {
        if (i == 0 || srtd[0][i].y - srtd[0][i - 1].y != 1 || srtd[0][i].x != srtd[0][i - 1].x)
            y++;
        dp[0][y]++;
        y_cmp[srtd[0][i]] = y;

        if (y_cmp[{srtd[0][i].x - 1, srtd[0][i].y}]) {
            graphs[0][y_cmp[{srtd[0][i].x - 1, srtd[0][i].y}]].insert(y);
            graphs[0][y].insert(y_cmp[{srtd[0][i].x - 1, srtd[0][i].y}]);
        }
    }
    FOR(i, 0, N) {
        if (i == 0 || srtd[1][i].y - srtd[1][i - 1].y != 1 || srtd[1][i].x != srtd[1][i - 1].x)
            x++;
        dp[1][x]++;
        x_cmp[srtd[1][i]] = x;

        if (x_cmp[{srtd[1][i].x - 1, srtd[1][i].y}]) {
            graphs[1][x_cmp[{srtd[1][i].x - 1, srtd[1][i].y}]].insert(x);
            graphs[1][x].insert(x_cmp[{srtd[1][i].x - 1, srtd[1][i].y}]);
        }
    }

    dfs1(0, 1);
    dfs1(1, 1);

    return (int)ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9976 KB Output is correct
2 Correct 12 ms 9976 KB Output is correct
3 Correct 13 ms 10232 KB Output is correct
4 Correct 12 ms 10104 KB Output is correct
5 Correct 14 ms 10232 KB Output is correct
6 Correct 13 ms 10104 KB Output is correct
7 Correct 15 ms 10360 KB Output is correct
8 Correct 14 ms 10104 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct
10 Correct 14 ms 10104 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12920 KB Output is correct
2 Correct 37 ms 12976 KB Output is correct
3 Correct 86 ms 17412 KB Output is correct
4 Correct 81 ms 17508 KB Output is correct
5 Correct 168 ms 24924 KB Output is correct
6 Correct 162 ms 25080 KB Output is correct
7 Correct 157 ms 25408 KB Output is correct
8 Correct 184 ms 24824 KB Output is correct
9 Correct 169 ms 25488 KB Output is correct
10 Correct 217 ms 32268 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15352 KB Output is correct
2 Correct 42 ms 14428 KB Output is correct
3 Correct 114 ms 23748 KB Output is correct
4 Correct 107 ms 21292 KB Output is correct
5 Correct 217 ms 37732 KB Output is correct
6 Correct 180 ms 29816 KB Output is correct
7 Correct 234 ms 38008 KB Output is correct
8 Correct 184 ms 30328 KB Output is correct
9 Correct 188 ms 28792 KB Output is correct
10 Correct 174 ms 28364 KB Output is correct