Submission #1198456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198456		totoro	Ideal city (IOI12_city)	C++20	100 / 100	160 ms	19384 KiB

city

#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

long long MOD = 1e9;

int n;

int ansFor(std::set<std::pair<int, int>> &coords) {
    std::map<std::pair<int, int>, int> colors;
    int cur = 0;
    std::vector<std::vector<int>> adj;
    std::vector<int> weight;
    for (auto [x, y] : coords) {
        // std::cout << x << ' ' << y << '\n';
        // std::cout << "(" << cur << ")\n";
        if (cur >= adj.size()) adj.emplace_back(), weight.emplace_back();

        if (coords.count(std::make_pair(x - 1, y)) && !(coords.count(std::make_pair(x - 1, y - 1)) && coords.count(std::make_pair(x, y - 1)))) {
            adj[cur].push_back(colors[std::make_pair(x - 1, y)]);
            adj[colors[std::make_pair(x - 1, y)]].push_back(cur);
        }

        colors[std::make_pair(x, y)] = cur;
        ++weight[cur];

        if (!coords.count(std::make_pair(x, y + 1))) ++cur;
    }

    // for (int i = 0; i < adj.size(); ++i) {
    //     std::cout << i << ':';
    //     for (int j : adj[i]) {
    //         std::cout << ' ' << j;
    //     }
    //     std::cout << '\n';
    // }

    long long ans = 0;
    auto dfs = [&](int node, int p, auto dfs) -> long long {
        long long myweight = weight[node];
        for (int to : adj[node]) {
            if (to == p) continue;
            myweight += dfs(to, node, dfs);
        }
        ans += (myweight) * (n - myweight);
        ans %= MOD;
        return myweight;
    };

    dfs(0, -1, dfs);
    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    n = N;
    std::set<std::pair<int, int>> normalcoords;
    for (int i = 0; i < N; ++i) {
        normalcoords.emplace(X[i], Y[i]);
    }

    long long ans = 0;
    ans += ansFor(normalcoords);
    ans %= MOD;

    std::set<std::pair<int, int>> flippedcoords;
    for (int i = 0; i < N; ++i) {
        flippedcoords.emplace(Y[i], X[i]);
    }

    ans += ansFor(flippedcoords);
    ans %= MOD;

    return ans;
}

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