oj.uz

Submission #66413

# Submission time Handle Problem Language Result Execution time Memory
66413 2018-08-10T12:17:01 Z aquablitz11 Ideal city (IOI12_city) C++14
100 / 100
 203 ms 22804 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<ll, int>;

const int N = 1e5+10;
const int MOD = 1e9;
const int INF = INT_MAX;
inline int add(int a, int b) { return (a+b)%MOD; }
inline int mul(int a, int b) { return (a*1ll*b)%MOD; }

int n, *X, *Y, ix[N], wei[N], sum[N], cost[N], total;
vector<int> G[N];
map<int, map<int, int>> comp;

void dfs(int u, int p)
{
    for (auto v : G[u]) if (v != p) {
        dfs(v, u);
        total = add(total, mul(add(cost[v], sum[v]), sum[u]));
        total = add(total, mul(add(cost[u], sum[u]), sum[v]));
        sum[u] = add(sum[u], sum[v]);
        cost[u] = add(cost[u], cost[v]);
    }
    cost[u] = add(cost[u], sum[u]);
    sum[u] = add(sum[u], wei[u]);
    total = add(total, mul(cost[u], wei[u]));
}

void solve()
{
    comp.clear();
    sort(ix, ix+n, [&] (int a, int b) {
        if (X[a] != X[b]) return X[a] < X[b];
        else return Y[a] < Y[b];
    });
    int px = -1, py = -1, cnt = 0;
    vector<pii> E;
    for (int i = 0; i < n; ++i) {
        int x = X[ix[i]], y = Y[ix[i]];
        if (x != px || y != py+1) {
            ++cnt;
            wei[cnt] = sum[cnt] = cost[cnt] = 0;
            G[cnt].clear();
        }
        ++wei[cnt];
        comp[x][y] = cnt;
        if (comp[x-1][y] > 0)
            E.emplace_back(comp[x-1][y], comp[x][y]);
        px = x, py = y;
    }
    sort(E.begin(), E.end());
    E.resize(unique(E.begin(), E.end()) - E.begin());
    for (auto e : E) {
        int u = e.first, v = e.second;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
}

int DistanceSum(int n, int *X, int *Y)
{
    ::n = n, ::X = X, ::Y = Y;
    for (int i = 0; i < n; ++i)
        ix[i] = i;
    solve();
    for (int i = 0; i < n; ++i)
        swap(X[i], Y[i]);
    solve();

    return total;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4572 KB Output is correct
2 Correct 35 ms 4744 KB Output is correct
3 Correct 76 ms 7284 KB Output is correct
4 Correct 68 ms 7916 KB Output is correct
5 Correct 147 ms 12276 KB Output is correct
6 Correct 175 ms 13164 KB Output is correct
7 Correct 168 ms 14224 KB Output is correct
8 Correct 159 ms 14616 KB Output is correct
9 Correct 161 ms 15912 KB Output is correct
10 Correct 191 ms 22768 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 22768 KB Output is correct
2 Correct 35 ms 22768 KB Output is correct
3 Correct 88 ms 22768 KB Output is correct
4 Correct 84 ms 22768 KB Output is correct
5 Correct 179 ms 22768 KB Output is correct
6 Correct 193 ms 22768 KB Output is correct
7 Correct 203 ms 22804 KB Output is correct
8 Correct 186 ms 22804 KB Output is correct
9 Correct 173 ms 22804 KB Output is correct
10 Correct 160 ms 22804 KB Output is correct