oj.uz

Submission #161658

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

const ll MOD = 1e9;

int N;
pair<int, int> sorted[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];
    }
}
void dfs2(int dir, int node, int parent = 0) {
    for (int i : graphs[dir][node]) if (i != parent) {
        dfs2(dir, i, node);
        ans = (ans + (N - dp[dir][i]) * dp[dir][i]) % MOD;
    }
}

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

    FOR(i, 0, N) {
        if (i == 0 || sorted[0][i].second - sorted[0][i - 1].second != 1 || sorted[0][i].first != sorted[0][i - 1].first) {
            y++;
        }
        dp[0][y]++;
        y_cmp[sorted[0][i]] = y;

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

        if (x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]) {
            graphs[1][x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]].insert(x);
            graphs[1][x].insert(x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]);
        }
    }

    dfs1(0, 1);
    dfs2(0, 1);
    dfs1(1, 1);
    dfs2(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 11 ms 9848 KB Output is correct
3 Correct 11 ms 9724 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 12 ms 9720 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 10 ms 9852 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 11 ms 9848 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 11 ms 9848 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 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 13 ms 10104 KB Output is correct
5 Correct 15 ms 10360 KB Output is correct
6 Correct 13 ms 10104 KB Output is correct
7 Correct 23 ms 10360 KB Output is correct
8 Correct 24 ms 10172 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct
10 Correct 13 ms 10104 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13028 KB Output is correct
2 Correct 39 ms 13092 KB Output is correct
3 Correct 85 ms 17784 KB Output is correct
4 Correct 80 ms 17868 KB Output is correct
5 Correct 170 ms 25824 KB Output is correct
6 Correct 161 ms 25788 KB Output is correct
7 Correct 160 ms 26360 KB Output is correct
8 Correct 189 ms 25584 KB Output is correct
9 Correct 174 ms 26224 KB Output is correct
10 Correct 221 ms 33152 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15608 KB Output is correct
2 Correct 44 ms 14584 KB Output is correct
3 Correct 123 ms 24304 KB Output is correct
4 Correct 104 ms 21716 KB Output is correct
5 Correct 236 ms 38396 KB Output is correct
6 Correct 181 ms 30584 KB Output is correct
7 Correct 250 ms 38832 KB Output is correct
8 Correct 186 ms 31028 KB Output is correct
9 Correct 193 ms 29628 KB Output is correct
10 Correct 184 ms 29084 KB Output is correct