Submission #551850

#	Time	Username	Problem	Language	Result	Execution time	Memory
551850		Jomnoi	Ideal city (IOI12_city)	C++17	100 / 100	121 ms	13828 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45