Submission #1249344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249344		domi	Ideal city (IOI12_city)	C++20	100 / 100	101 ms	16144 KiB

city

#include <bits/stdc++.h>

const int MOD = 1e9;

using namespace std;

int n;

int solve(map<int, vector<int>>& mp) {
    vector<vector<int>> T;
    map<pair<int, int>, int> id;
    vector<int> s;
    int cnt = -1;
    int idx = 0;

    for (auto &[v, ap] : mp) {
        sort(ap.begin(), ap.end());
        ++idx;

        for (int i = 0; i < (int)ap.size(); ++i) {
            if (i == 0 || ap[i] != ap[i - 1] + 1) {
                ++cnt;
                T.push_back({});
                s.push_back(0);
            }

            id[{v, ap[i]}] = cnt;
            ++s.back();

            auto it_prev = id.find({v - 1, ap[i]});
            if (idx != 1 && it_prev != id.end()) {
                int neigh = it_prev->second;
                if (cnt < (int)T.size() && neigh < (int)T.size()) {
                    if (T[cnt].empty() || neigh != T[cnt].back()) {
                        T[cnt].push_back(neigh);
                        T[neigh].push_back(cnt);
                    }
                }
            }
        }
    }

    vector<int> SZ(cnt + 1, 0);
    long long ans = 0;

    function<void(int, int)> dfs = [&](int nod, int p) {
        SZ[nod] = s[nod];
        for (int son : T[nod]) {
            if (son == p) continue;
            dfs(son, nod);
            SZ[nod] += SZ[son];
            ans += 1LL * (n - SZ[son]) * SZ[son];
        }
    };

    dfs(0, -1);
    return (int)(ans % MOD);
}

int DistanceSum(int N, int *X, int *Y) {
    n = N;
    map<int, vector<int>> lin, col;

    for (int i = 0; i < n; ++i) {
        col[X[i]].push_back(Y[i]);
        lin[Y[i]].push_back(X[i]);
    }

    return (solve(lin) + solve(col)) % MOD;
}

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