Submission #66412

#	Time	Username	Problem	Language	Result	Execution time	Memory
66412		aquablitz11	Ideal city (IOI12_city)	C++14	32 / 100	8 ms	1800 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45