Submission #382774

#	Time	Username	Problem	Language	Result	Execution time	Memory
382774		ParsaAlizadeh	Ideal city (IOI12_city)	C++17	100 / 100	102 ms	14176 KiB

city

#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 1e5 + 10;
constexpr int MOD = 1e9;

int n, par[N], sz[N];
vector<int> A, B;
vector<int> row[N], col[N];
vector<int> adj[N];

ll ans;

void add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void DFS(int u, int p) {
    for (int v : adj[u]) if (v != p) {
        DFS(v, u);
        ans += (ll) sz[v] * (n - sz[v]);
        sz[u] += sz[v];
    }
}

int DistanceSum(int n_, int *X, int *Y) {
    n = n_;
    for (int i = 0; i < n; i++) {
        A.push_back(X[i]);
        B.push_back(Y[i]);
    }
    sort(all(A)); A.erase(unique(all(A)), A.end());
    sort(all(B)); B.erase(unique(all(B)), B.end());
    for (int i = 0; i < n; i++) {
        X[i] = lower_bound(all(A), X[i]) - A.begin();
        Y[i] = lower_bound(all(B), Y[i]) - B.begin();
        row[X[i]].push_back(i);
        col[Y[i]].push_back(i);
    }
    for (int i = 0; i < A.size(); i++) {
        sort(all(row[i]), [&Y] (int i, int j) { return Y[i] < Y[j]; });
    }
    for (int i = 0; i < B.size(); i++) {
        sort(all(col[i]), [&X] (int i, int j) { return X[i] < X[j]; });
    }

    // =========== X Axis ============
    iota(par, par + n, 0);
    fill(sz, sz + n, 1);
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < row[i].size(); j++) {
            if (j && Y[row[i][j - 1]] + 1 == Y[row[i][j]]) {
                par[row[i][j]] = par[row[i][j - 1]];
                sz[par[row[i][j]]]++;
            }
        }
    }
    for (int i = 1; i < A.size(); i++) {
        int ptr = 0;
        for (int j = 0; j < row[i].size(); j++) {
            while (ptr < row[i - 1].size() && Y[row[i - 1][ptr]] < Y[row[i][j]])
                ptr++;
            if (ptr == row[i - 1].size())
                break;
            if (Y[row[i - 1][ptr]] != Y[row[i][j]])
                continue;
            if (j == 0 || par[row[i][j - 1]] != par[row[i][j]] || ptr == 0 || par[row[i - 1][ptr - 1]] != par[row[i - 1][ptr]]) {
                add_edge(par[row[i][j]], par[row[i - 1][ptr]]);
            }
        }
    }
    DFS(par[0], -1);

    // =========== Y Axis ============
    iota(par, par + n, 0);
    fill(sz, sz + n, 1);
    for (int i = 0; i < n; i++)
        adj[i].clear();
    for (int i = 0; i < B.size(); i++) {
        for (int j = 0; j < col[i].size(); j++) {
            if (j && X[col[i][j - 1]] + 1 == X[col[i][j]]) {
                par[col[i][j]] = par[col[i][j - 1]];
                sz[par[col[i][j]]]++;
            }
        }
    }
    for (int i = 1; i < B.size(); i++) {
        int ptr = 0;
        for (int j = 0; j < col[i].size(); j++) {
            while (ptr < col[i - 1].size() && X[col[i - 1][ptr]] < X[col[i][j]])
                ptr++;
            if (ptr == col[i - 1].size())
                break;
            if (X[col[i - 1][ptr]] != X[col[i][j]])
                continue;
            if (j == 0 || par[col[i][j - 1]] != par[col[i][j]] || ptr == 0 || par[col[i - 1][ptr - 1]] != par[col[i - 1][ptr]]) {
                add_edge(par[col[i][j]], par[col[i - 1][ptr]]);
            }
        }
    }
    DFS(par[0], -1);

    return ans % MOD;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < B.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < row[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
city.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 1; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < row[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
city.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             while (ptr < row[i - 1].size() && Y[row[i - 1][ptr]] < Y[row[i][j]])
      |                    ~~~~^~~~~~~~~~~~~~~~~~~
city.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             if (ptr == row[i - 1].size())
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
city.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < B.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = 0; j < col[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
city.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < B.size(); i++) {
      |                     ~~^~~~~~~~~~
city.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int j = 0; j < col[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
city.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while (ptr < col[i - 1].size() && X[col[i - 1][ptr]] < X[col[i][j]])
      |                    ~~~~^~~~~~~~~~~~~~~~~~~
city.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             if (ptr == col[i - 1].size())
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~

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