oj.uz

Submission #103803

# Submission time Handle Problem Language Result Execution time Memory
103803 2019-04-02T17:43:20 Z alexpetrescu Ideal city (IOI12_city) C++14
100 / 100
 215 ms 14588 KB 
#include <algorithm>
#include <utility>
#include <vector>
#include <map>

#define x first
#define y second

#define MOD 1000000000

void dfs(int x, std::vector < bool > &viz, std::vector < std::vector < int > > &g, std::vector < int > &sum) {
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y] == 0) {
            dfs(y, viz, g, sum);
            sum[x] += sum[y];
        }
    }
}

inline int solve(int n, int *X, int *Y) {
    std::vector < std::pair < int, int > > v(n);
    for (int i = 0; i < n; i++)
        v[i] = {X[i], Y[i]};
    std::sort(v.begin(), v.end());

    int k = 1;
    std::vector < int > boss(n, 1);
    for (int i = 1; i < n; i++)
        if (v[i].x == v[i - 1].x && v[i].y == v[i - 1].y + 1)
            boss[i] = boss[i - 1];
        else
            boss[i] = ++k;

    std::map < std::pair < int, int > , int > mp;
    std::vector < int > sum(k + 1, 0);
    for (int i = 0; i < n; i++)
        mp[v[i]] = boss[i], sum[boss[i]]++;

    std::vector < std::vector < int > > g(k + 1);
    std::vector < int > last(k + 1, 0);
    for (int i = 0; i < n; i++) {
        int x = mp[{v[i].x - 1, v[i].y}];
        if (x && last[boss[i]] != x) {
            last[boss[i]] = x;
            g[boss[i]].push_back(x);
            g[x].push_back(boss[i]);
        }
    }

    std::vector < bool > viz(k + 1, 0);
    int rad = 1;
    dfs(rad, viz, g, sum);

    int ans = 0;
    for (int i = 1; i <= k; i++)
        ans = (ans + 1LL * sum[i] * (n - sum[i])) % MOD;
    return ans;
}

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

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2160 KB Output is correct
2 Correct 23 ms 2176 KB Output is correct
3 Correct 63 ms 5016 KB Output is correct
4 Correct 64 ms 4984 KB Output is correct
5 Correct 135 ms 9484 KB Output is correct
6 Correct 132 ms 9540 KB Output is correct
7 Correct 135 ms 9860 KB Output is correct
8 Correct 138 ms 9396 KB Output is correct
9 Correct 137 ms 9796 KB Output is correct
10 Correct 143 ms 13936 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3268 KB Output is correct
2 Correct 29 ms 2904 KB Output is correct
3 Correct 82 ms 7416 KB Output is correct
4 Correct 74 ms 6628 KB Output is correct
5 Correct 215 ms 14444 KB Output is correct
6 Correct 159 ms 11520 KB Output is correct
7 Correct 180 ms 14588 KB Output is correct
8 Correct 148 ms 11612 KB Output is correct
9 Correct 151 ms 10952 KB Output is correct
10 Correct 142 ms 10744 KB Output is correct