oj.uz

Submission #707917

# Submission time Handle Problem Language Result Execution time Memory
707917 2023-03-10T13:26:20 Z Nhoksocqt1 Ideal city (IOI12_city) C++17
100 / 100
 66 ms 10356 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;
const int modl = 1000000000;

vector<int> adj[MAXN];
ii block[MAXN];
int id[MAXN], sz[MAXN], numNode;

int dfs(int u, int p) {
    ll res(0);
    for (int it = 0; it < int(adj[u].size()); ++it) {
        int v(adj[u][it]);
        if(v != p) {
            res = (res + dfs(v, u)) % modl;
            sz[u] += sz[v];
            //cout << u << ' ' << v << ' ' << sz[v] << ' ' << numNode - sz[v] << '\n';
            res = (res + 1LL * sz[v] * (numNode - sz[v])) % modl;
        }
    }

    return res;
}

int calc(void) {
    sort(block + 1, block + numNode + 1);
    for (int i = 1; i <= numNode; ++i)
        adj[i].clear(), id[i] = sz[i] = 0;

    id[0] = 0;
    block[0] = {-1, -1};
    for (int i = 1; i <= numNode; ++i) {
        if(block[i].fi == block[i - 1].fi && block[i].se == 1 + block[i - 1].se) {
            id[i] = id[i - 1];
        } else {
            id[i] = ++id[0];
        }

        ++sz[id[i]];

        int j = lower_bound(block + 1, block + numNode + 1, ii(block[i].fi - 1, block[i].se)) - block;
        if(block[j] == ii(block[i].fi - 1, block[i].se)) {
            adj[id[j]].push_back(id[i]);
            adj[id[i]].push_back(id[j]);
        }
    }

    for (int i = 1; i <= numNode; ++i) {
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }

    //cout << '\n';
    return dfs(1, -1);
}

int DistanceSum(int _N, int _X[], int _Y[]) {
    numNode = _N;
    for (int i = 1; i <= numNode; ++i)
        block[i] = {_X[i - 1], _Y[i - 1]};

    ll res = calc();
    for (int i = 1; i <= numNode; ++i)
        swap(block[i].fi, block[i].se);

    return (res + calc()) % modl;
}

Compilation message

city.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
city.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3412 KB Output is correct
2 Correct 11 ms 3796 KB Output is correct
3 Correct 26 ms 4796 KB Output is correct
4 Correct 26 ms 5260 KB Output is correct
5 Correct 57 ms 7116 KB Output is correct
6 Correct 57 ms 7888 KB Output is correct
7 Correct 54 ms 7980 KB Output is correct
8 Correct 54 ms 7060 KB Output is correct
9 Correct 49 ms 7656 KB Output is correct
10 Correct 50 ms 10356 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3520 KB Output is correct
2 Correct 13 ms 3808 KB Output is correct
3 Correct 28 ms 5084 KB Output is correct
4 Correct 33 ms 5204 KB Output is correct
5 Correct 66 ms 7612 KB Output is correct
6 Correct 53 ms 7784 KB Output is correct
7 Correct 59 ms 7716 KB Output is correct
8 Correct 55 ms 7652 KB Output is correct
9 Correct 57 ms 7448 KB Output is correct
10 Correct 54 ms 7568 KB Output is correct