oj.uz

Submission #337465

# Submission time Handle Problem Language Result Execution time Memory
337465 2020-12-20T23:24:26 Z thecodingwizard Ideal city (IOI12_city) C++11
100 / 100
 739 ms 19816 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5228 KB Output is correct
2 Correct 6 ms 5100 KB Output is correct
3 Correct 7 ms 5228 KB Output is correct
4 Correct 7 ms 5228 KB Output is correct
5 Correct 8 ms 5356 KB Output is correct
6 Correct 9 ms 5228 KB Output is correct
7 Correct 8 ms 5356 KB Output is correct
8 Correct 9 ms 5228 KB Output is correct
9 Correct 9 ms 5228 KB Output is correct
10 Correct 8 ms 5228 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7144 KB Output is correct
2 Correct 74 ms 7144 KB Output is correct
3 Correct 220 ms 10248 KB Output is correct
4 Correct 221 ms 10220 KB Output is correct
5 Correct 631 ms 15388 KB Output is correct
6 Correct 647 ms 15464 KB Output is correct
7 Correct 705 ms 15720 KB Output is correct
8 Correct 665 ms 15464 KB Output is correct
9 Correct 668 ms 15720 KB Output is correct
10 Correct 582 ms 19816 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7912 KB Output is correct
2 Correct 77 ms 7784 KB Output is correct
3 Correct 260 ms 12140 KB Output is correct
4 Correct 246 ms 11500 KB Output is correct
5 Correct 688 ms 19176 KB Output is correct
6 Correct 739 ms 16872 KB Output is correct
7 Correct 684 ms 19176 KB Output is correct
8 Correct 724 ms 16872 KB Output is correct
9 Correct 701 ms 16616 KB Output is correct
10 Correct 704 ms 16360 KB Output is correct