oj.uz

답안 #140508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140508 2019-08-03T09:16:29 Z darkkcyan 이상적인 도시 (IOI12_city) C++14
100 / 100
 397 ms 19456 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }


int DistanceSum(int n, int *x, int *y) {
    map<pair<int, int>, int> points;
    rep(i, n) points[{x[i], y[i]}] = i;

    struct Dsu {
        mutable vector<int> root;
        vector<int> cnt;
        Dsu(int n_): root(n_), cnt(n_, 1) {
            rep(i, len(root)) root[i] = i;
        }

        int find_set(int u) const { return u == root[u] ? u : root[u] = find_set(root[u]); }
        void join(int u, int v) {
            u = find_set(u);
            v = find_set(v);
            if (u == v) return;
            if (rand() & 1) swap(u, v);
            root[u] = v;
            cnt[v] += cnt[u];
        }

        int set_count(int u) { return cnt[find_set(u)]; }
    };

    const int dx[] = {0, 1};
    const int dy[] = {1, 0};

    llong ans = 0;
    rep(dir, 2) {
        Dsu dsu(n);
        rep(i, n) {
            if (points.count({x[i] + dx[dir], y[i] + dy[dir]})) {
                dsu.join(points[{x[i] + dx[dir], y[i] + dy[dir]}], i);
            }
        }
        vector<set<int>> gr(n);
        rep(i, n) {
            auto f = points.find({x[i] + dx[!dir], y[i] + dy[!dir]});
            if (f == points.end()) continue;
            int u = dsu.find_set(i);
            int v = dsu.find_set(f->yy);
            gr[u].insert(v);
            gr[v].insert(u);
        }

        vector<int> tree_size = dsu.cnt;
        function<void(int, int)> dfs = [&](int u, int p) {
            for (auto v: gr[u]) {
                if (v == p) continue;
                dfs(v, u);
                tree_size[u] += tree_size[v];
                ans += 1ll * tree_size[v] * (n - tree_size[v]);
            }
        };
        dfs(dsu.find_set(0), -1);
    }

    return (int)(ans % (1000 * 1000 * 1000));
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 6 ms 696 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 696 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 632 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 3192 KB Output is correct
2 Correct 48 ms 3196 KB Output is correct
3 Correct 134 ms 7424 KB Output is correct
4 Correct 140 ms 7380 KB Output is correct
5 Correct 350 ms 14340 KB Output is correct
6 Correct 356 ms 14272 KB Output is correct
7 Correct 328 ms 14584 KB Output is correct
8 Correct 382 ms 14180 KB Output is correct
9 Correct 351 ms 14584 KB Output is correct
10 Correct 333 ms 19456 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 3904 KB Output is correct
2 Correct 45 ms 3828 KB Output is correct
3 Correct 152 ms 9152 KB Output is correct
4 Correct 155 ms 8496 KB Output is correct
5 Correct 397 ms 18040 KB Output is correct
6 Correct 338 ms 15748 KB Output is correct
7 Correct 390 ms 18052 KB Output is correct
8 Correct 376 ms 15876 KB Output is correct
9 Correct 393 ms 15524 KB Output is correct
10 Correct 346 ms 15236 KB Output is correct