oj.uz

Submission #229340

# Submission time Handle Problem Language Result Execution time Memory
229340 2020-05-04T09:06:18 Z PeppaPig Ideal city (IOI12_city) C++14
100 / 100
 155 ms 24544 KB 
#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;
const int M = 1e9;

int n, id[N], sz[N];
long dp[N], ans;
vector<set<int> > g;

long dfs(int u, int p) {
    long cnt = sz[u];
    for(int v : g[u]) if(v != p) {
        long z = dfs(v, u);
        ans = (ans + (dp[v] + z) * cnt + dp[u] * z) % M;
        dp[u] = (dp[u] + dp[v] + z) % M;
        cnt = (cnt + z) % M;
    }
    return cnt;
}

void solve(int *X, int *Y) {
    memset(id, 0, sizeof id), memset(sz, 0, sizeof sz);
    memset(dp, 0, sizeof dp);
    g = vector<set<int> >(N);

    vector<pii> vec;
    for(int i = 0; i < n; i++) vec.emplace_back(X[i], Y[i]);
    sort(vec.begin(), vec.end());

    map<pii, int> mp;
    for(int i = 0, ptr = 0; i < n; i++) {
        mp[vec[i]] = i;
        if(i == 0 || vec[i - 1].x != vec[i].x || vec[i - 1].y + 1 != vec[i].y)
            id[i] = ++ptr;
        else id[i] = id[i-1];
        ++sz[id[i]];
        if(mp.count(pii(vec[i].x - 1, vec[i].y))) {
            int v = id[mp[pii(vec[i].x - 1, vec[i].y)]];
            g[id[i]].emplace(v), g[v].emplace(id[i]);
        }
    }

    dfs(1, 0);
}

int DistanceSum(int _n, int *X, int *Y) {
    n = _n;
    solve(X, Y), solve(Y, X);
    return ans; 
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13020 KB Output is correct
2 Correct 34 ms 13020 KB Output is correct
3 Correct 72 ms 15340 KB Output is correct
4 Correct 70 ms 15468 KB Output is correct
5 Correct 132 ms 19296 KB Output is correct
6 Correct 134 ms 19424 KB Output is correct
7 Correct 130 ms 19548 KB Output is correct
8 Correct 130 ms 19168 KB Output is correct
9 Correct 137 ms 19680 KB Output is correct
10 Correct 151 ms 24544 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13660 KB Output is correct
2 Correct 35 ms 13404 KB Output is correct
3 Correct 74 ms 17132 KB Output is correct
4 Correct 76 ms 16492 KB Output is correct
5 Correct 154 ms 23008 KB Output is correct
6 Correct 142 ms 20704 KB Output is correct
7 Correct 155 ms 23264 KB Output is correct
8 Correct 141 ms 20960 KB Output is correct
9 Correct 142 ms 20472 KB Output is correct
10 Correct 135 ms 20192 KB Output is correct