oj.uz

Submission #66412

# Submission time Handle Problem Language Result Execution time Memory
66412 2018-08-10T12:16:27 Z aquablitz11 Ideal city (IOI12_city) C++14
32 / 100
 8 ms 1800 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int N = 2e3+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 2 ms 376 KB Output is correct
2 Correct 3 ms 548 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 736 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 872 KB Output is correct
2 Correct 4 ms 912 KB Output is correct
3 Correct 4 ms 936 KB Output is correct
4 Correct 5 ms 1092 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 6 ms 1172 KB Output is correct
8 Correct 6 ms 1172 KB Output is correct
9 Correct 4 ms 1172 KB Output is correct
10 Correct 6 ms 1172 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -