oj.uz

Submission #382774

# Submission time Handle Problem Language Result Execution time Memory
382774 2021-03-28T07:36:16 Z ParsaAlizadeh Ideal city (IOI12_city) C++17
100 / 100
 102 ms 14176 KB 
#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

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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 7 ms 7404 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 7 ms 7532 KB Output is correct
6 Correct 7 ms 7532 KB Output is correct
7 Correct 7 ms 7532 KB Output is correct
8 Correct 7 ms 7532 KB Output is correct
9 Correct 7 ms 7532 KB Output is correct
10 Correct 7 ms 7532 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8300 KB Output is correct
2 Correct 18 ms 8300 KB Output is correct
3 Correct 36 ms 9320 KB Output is correct
4 Correct 40 ms 9320 KB Output is correct
5 Correct 71 ms 11360 KB Output is correct
6 Correct 69 ms 11232 KB Output is correct
7 Correct 73 ms 11232 KB Output is correct
8 Correct 69 ms 11232 KB Output is correct
9 Correct 70 ms 11104 KB Output is correct
10 Correct 87 ms 14176 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8684 KB Output is correct
2 Correct 20 ms 8556 KB Output is correct
3 Correct 52 ms 10344 KB Output is correct
4 Correct 42 ms 9960 KB Output is correct
5 Correct 101 ms 13124 KB Output is correct
6 Correct 82 ms 12000 KB Output is correct
7 Correct 102 ms 13280 KB Output is correct
8 Correct 83 ms 12000 KB Output is correct
9 Correct 78 ms 11616 KB Output is correct
10 Correct 76 ms 11488 KB Output is correct