oj.uz

답안 #550805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
550805 2022-04-19T08:50:29 Z elazarkoren 이상적인 도시 (IOI12_city) C++17
100 / 100
 339 ms 13628 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 448 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 4 ms 480 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2460 KB Output is correct
2 Correct 32 ms 2380 KB Output is correct
3 Correct 94 ms 5332 KB Output is correct
4 Correct 97 ms 5444 KB Output is correct
5 Correct 247 ms 10444 KB Output is correct
6 Correct 339 ms 10388 KB Output is correct
7 Correct 228 ms 10376 KB Output is correct
8 Correct 245 ms 10352 KB Output is correct
9 Correct 299 ms 10264 KB Output is correct
10 Correct 236 ms 13628 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2616 KB Output is correct
2 Correct 36 ms 2544 KB Output is correct
3 Correct 120 ms 5952 KB Output is correct
4 Correct 134 ms 5756 KB Output is correct
5 Correct 310 ms 11468 KB Output is correct
6 Correct 280 ms 10852 KB Output is correct
7 Correct 322 ms 11732 KB Output is correct
8 Correct 293 ms 10920 KB Output is correct
9 Correct 293 ms 10624 KB Output is correct
10 Correct 294 ms 10508 KB Output is correct