Submission #1197664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197664		Hamed_Ghaffari	Ideal city (IOI12_city)	C++20	100 / 100	120 ms	14228 KiB

city

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5, MOD = 1e9;

int n;
pii a[MXN];
int N, w[MXN];
vector<int> g[MXN];
map<pii, int> cmp;
int ans;

void dfs(int v, int p=-1) {
    for(int u : g[v])
        if(u!=p) {
            dfs(u, v);
            w[v] += w[u];
            (ans += 1ll*w[u]*(n-w[u])%MOD) %= MOD;
        }
}

void solve() {
    sort(a, a+n);
    for(int i=0, j; i<n;) {
        j=i;
        while(j+1<n && a[j+1].X==a[i].X && a[j+1].Y==a[j].Y+1) j++;
        for(int k=i; k<=j; k++)
            w[cmp[a[k]] = N]++;
        N++;
        i = j+1;
    }
    pii lst = {-1, -1}, cur;
    for(int i=0; i<n; i++)
        if(cmp.find({a[i].X-1, a[i].Y})!=cmp.end()) {
            cur = {cmp[{a[i].X-1, a[i].Y}], cmp[a[i]]};
            if(lst!=cur) {
                g[cur.X].push_back(cur.Y);
                g[cur.Y].push_back(cur.X);
                lst = cur;
            }
        }
    dfs(0);
    for(int i=0; i<N; i++) {
        w[i] = 0;
        g[i].clear();
    }
    cmp.clear();
    N = 0;
}

int DistanceSum(int n, int *A, int *B) {
    ::n = n;
    for(int i=0; i<n; i++) a[i] = {A[i], B[i]};
    solve();
    for(int i=0; i<n; i++) swap(a[i].X, a[i].Y);
    solve();
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45