Submission #550805

#	Time	Username	Problem	Language	Result	Execution time	Memory
550805		elazarkoren	이상적인 도시 (IOI12_city)	C++17	100 / 100	339 ms	13628 KiB

city

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int mod = 1e9;
const int MAX_N = 1e5 + 5;

set<pair<pii, int>> points;
int n;

int component[MAX_N];
int sz[MAX_N];

ll ans = 0;

int Dfs(vvi &tree, int node, int parent) {
    int size = sz[node];
    for (int neighbor : tree[node]) {
        if (neighbor == parent) continue;
        int son_sz = Dfs(tree, neighbor, node);
        size += son_sz;
        ans += ll(n - son_sz) * son_sz % mod;
        ans %= mod;
    }
    return size;
}

int Solve(int *x, int *y) {
    points.clear();
    vi ind(n);
    for (int i = 0; i < n; i++) {
        points.insert({{x[i], y[i]}, i});
        ind[i] = i;
    }
    sort(all(ind), [&] (int i, int j) {
        return (x[i] == x[j] ? y[i] < y[j] : x[i] < x[j]);
    });
    int size = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        component[ind[i]] = size;
        sz[size] = 1;
        while (j + 1 < n && x[ind[j + 1]] == x[ind[j]] && y[ind[j + 1]] == y[ind[j]] + 1) {
            component[ind[++j]] = size;
            sz[size]++;
        }
        size++;
        i = j;
    }
    vvi tree(size);
    for (int i = 0; i < n; i++) {
        auto it = points.lower_bound({{x[i] - 1, y[i]}, -1});
        if (it != points.end() && it->x == pii{x[i] - 1, y[i]}) {
            tree[component[i]].push_back(component[it->y]);
        }
        it = points.lower_bound({{x[i] + 1, y[i]}, -1});
        if (it != points.end() && it->x == pii(x[i] + 1, y[i])) {
            tree[component[i]].push_back(component[it->y]);
        }
    }
    for (int i = 0; i < size; i++) {
        sort(all(tree[i]));
        tree[i].erase(unique(all(tree[i])), tree[i].end());
    }
    ans = 0;
    Dfs(tree, 0, -1);
    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    n = N;
    return (Solve(X, Y) + Solve(Y, X)) % mod;
}
//11
//2 5
//2 6
//3 3
//3 6
//4 3
//4 4
//4 5
//4 6
//5 3
//5 4
//5 6

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