Submission #707916

#	Time	Username	Problem	Language	Result	Execution time	Memory
707916		Nhoksocqt1	Ideal city (IOI12_city)	C++17	32 / 100	16 ms	3676 KiB

city

#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 = 1000000007;

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

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