Submission #1156176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156176		Sharky	Ideal city (IOI12_city)	C++20	100 / 100	89 ms	16180 KiB

city

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

#define int long long

const int N = 1e5 + 5;
int node;
vector<int> g[N];
map<int, vector<int>> h, v;
map<int, vector<array<int, 3>>> mh;
int k = 0, ans = 0, cur = 0, tot = 0;
int sz[N];

const int mod = 2e9;

void init(int u, int p, int pd = 0) {
    cur += pd * sz[u];
    cur %= mod;
    for (int v : g[u]) {
        if (v == p) continue;
        init(v, u, pd + 1);
        sz[u] += sz[v];
    }
}

void dfs(int u, int p) {
    int sc = 0;
    for (int v : g[u]) if (v != p) sc += sz[v];
    ans += cur * (sz[u] - sc) % mod;
    ans %= mod;
    sort(g[u].begin(), g[u].end());
    g[u].erase(unique(g[u].begin(), g[u].end()), g[u].end());
    for (int v : g[u]) {
        if (v == p) continue;
        cur += (node - 2 * sz[v]);
        cur %= mod;
        dfs(v, u);
        cur -= (node - 2 * sz[v]);
        (cur += mod) %= mod;
    }
}

int32_t DistanceSum(int32_t n, int32_t *x, int32_t *y) {
    node = n;
    for (int i = 0; i < n; i++) {
        h[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    for (int iter = 0; iter < 2; iter++) {
        for (auto& [key, vec] : h) {
            sort(vec.begin(), vec.end());
            for (int& x : vec) {
                if (!mh[key].empty() && mh[key].back()[1] + 1 == x) mh[key].back()[1]++, sz[mh[key].back()[2]]++;
                else mh[key].push_back({x, x, ++k}), sz[k]++;
            }
        }
        for (auto& [key, b] : mh) {
            if (!mh.count(key - 1)) continue;
            vector<array<int, 3>> a = mh[key - 1];
            for (auto& [x, y, id] : b) {
                int l = 0, r = a.size() - 1;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (a[mid][1] < x) l = mid;
                    else r = mid - 1;
                }
                for (int i = l + !!(a[l][1] < x); i < a.size(); i++) {
                    auto [L, R, idx] = a[i];
                    if (R < x || y < L) break;
                    g[idx].push_back(id);
                    g[id].push_back(idx);
                }
            }
        }
        init(1, -1);
        dfs(1, -1);
        tot += ans;
        tot %= mod;
        k = ans = cur = 0;
        for (int i = 0; i < N; i++) sz[i] = 0, g[i].clear();
        h.swap(v);
        mh.clear();
    }
    return tot / 2;
}

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