Submission #337465

#	Time	Username	Problem	Language	Result	Execution time	Memory
337465		thecodingwizard	Ideal city (IOI12_city)	C++11	100 / 100	739 ms	19816 KiB

city

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

using ll = long long;

#define mod 1000000000
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define F0R(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()

int n;
vector<ii> A;

set<int> adj[100000];

int pa[100000], sz[100000];
int get(int x) { return pa[x] == x ? x : pa[x] = get(pa[x]); }
void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
}

ll ans = 0;
ll subtreeSum[100000];
int dfs1(int u, int p) {
    subtreeSum[u] = sz[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        subtreeSum[u] += dfs1(v, u);
    }
    return subtreeSum[u];
}
void dfs2(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            ll x = subtreeSum[v], y = n - subtreeSum[v];
            ans += x*y;
            ans %= mod;
            dfs2(v, u);
        }
    }
}
void solve() {
    map<ii, int> points;
    F0R(i, n) {
        points[A[i]] = i;
        adj[i].clear();
        pa[i] = i; sz[i] = 1;
        subtreeSum[i] = 0;
    }

    F0R(i, n) {
        if (points.count(mp(A[i].f, A[i].s-1))) unite(i, points[mp(A[i].f, A[i].s-1)]);
        if (points.count(mp(A[i].f, A[i].s+1))) unite(i, points[mp(A[i].f, A[i].s+1)]);
    }
    F0R(i, n) {
        if (points.count(mp(A[i].f-1, A[i].s))) adj[get(i)].insert(get(points[mp(A[i].f-1, A[i].s)]));
        if (points.count(mp(A[i].f+1, A[i].s))) adj[get(i)].insert(get(points[mp(A[i].f+1, A[i].s)]));
    }

    dfs1(get(0), -1);
    dfs2(get(0), -1);
}

int DistanceSum(int N, int *X, int *Y) {
    n = N;
    F0R(i, n) {
        A.pb(mp(X[i], Y[i]));
    }
    solve();
    A.clear();
    F0R(i, n) {
        A.pb(mp(Y[i], X[i]));
    }
    solve();
    return ans;
}

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