oj.uz

Submission #551850

# Submission time Handle Problem Language Result Execution time Memory
551850 2022-04-21T18:00:21 Z Jomnoi Ideal city (IOI12_city) C++17
100 / 100
 121 ms 13828 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int MAX_N = 1e5 + 10;
const int MOD = 1e9;

int n, ans;
int sz[MAX_N], parent[MAX_N], sub[MAX_N];
set <int> graph[MAX_N];

class Block {
public :
    int x, y, i;
    Block() {}
    Block(const int &x_, const int &y_, const int &i_) : x(x_), y(y_), i(i_) {}

    bool operator<(const Block &o) const {
        return make_pair(x, y) < make_pair(o.x, o.y);
    }
};

int root(const int &u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

void merge(const int &a, const int &b) {
    int u = root(a), v = root(b);
    if(u == v) {
        return;
    }

    if(sz[u] < sz[v]) {
        swap(u, v);
    }
    sz[u] += sz[v];
    parent[v] = u;
}

void addEdge(const int &u, const int &v) {
    graph[u].insert(v);
    graph[v].insert(u);
}

int dfs(const int &u, const int &p) {
    sub[u] = sz[u];
    for(auto v : graph[u]) {
        if(v == p) {
            continue;
        }

        sub[u] += dfs(v, u);
    }
    ans += 1ll*sub[u] * (n - sub[u]) % MOD;
    ans %= MOD;
    return sub[u];
}

int solve(int N, int *X, int *Y) {
    n = N;
    for(int i = 1; i <= N; i++) {
        parent[i] = i;
        sz[i] = 1;
        graph[i].clear();
    }

    vector <Block> vec;
    for(int i = 0; i < N; i++) {
        vec.push_back(Block(X[i], Y[i], i + 1));
    }

    sort(vec.begin(), vec.end());

    for(int i = 1; i < vec.size(); i++) {
        if(vec[i].x == vec[i - 1].x and vec[i - 1].y + 1 == vec[i].y) {
            merge(vec[i].i, vec[i - 1].i);
        }
    }
    for(int i = 0; i < vec.size(); i++) {
        auto it = lower_bound(vec.begin(), vec.end(), Block(vec[i].x - 1, vec[i].y, 0));
        if(it != vec.end() and it->x + 1 == vec[i].x and it->y == vec[i].y) {
            addEdge(root(it->i), root(vec[i].i));
        }
        it = lower_bound(vec.begin(), vec.end(), Block(vec[i].x + 1, vec[i].y, 0));
        if(it != vec.end() and it->x - 1 == vec[i].x and it->y == vec[i].y) {
            addEdge(root(it->i), root(vec[i].i));
        }
    }

    if(DEBUG) {
        cout << "DEBUG\n";
        for(int i = 1; i <= N; i++) {
            if(i == root(i)) {
                cout << i << " : " << sz[i] << endl;
            }
        }
    }

    ans = 0;
    dfs(root(1), -1);

    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    return (solve(N, X, Y) + solve(N, Y, X)) % MOD;
}

Compilation message

city.cpp: In function 'int solve(int, int*, int*)':
city.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 1; i < vec.size(); i++) {
      |                    ~~^~~~~~~~~~~~
city.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0; i < vec.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5008 KB Output is correct
2 Correct 4 ms 5008 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 5020 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5128 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6192 KB Output is correct
2 Correct 18 ms 6168 KB Output is correct
3 Correct 40 ms 7720 KB Output is correct
4 Correct 41 ms 7736 KB Output is correct
5 Correct 81 ms 10472 KB Output is correct
6 Correct 84 ms 10604 KB Output is correct
7 Correct 83 ms 10796 KB Output is correct
8 Correct 82 ms 10456 KB Output is correct
9 Correct 83 ms 10608 KB Output is correct
10 Correct 88 ms 13828 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6556 KB Output is correct
2 Correct 21 ms 6372 KB Output is correct
3 Correct 58 ms 8916 KB Output is correct
4 Correct 50 ms 8240 KB Output is correct
5 Correct 114 ms 12788 KB Output is correct
6 Correct 96 ms 11036 KB Output is correct
7 Correct 121 ms 13268 KB Output is correct
8 Correct 96 ms 10996 KB Output is correct
9 Correct 93 ms 10796 KB Output is correct
10 Correct 93 ms 10872 KB Output is correct