Submission #103803

#	Time	Username	Problem	Language	Result	Execution time	Memory
103803		alexpetrescu	Ideal city (IOI12_city)	C++14	100 / 100	215 ms	14588 KiB

city

#include <algorithm>
#include <utility>
#include <vector>
#include <map>

#define x first
#define y second

#define MOD 1000000000

void dfs(int x, std::vector < bool > &viz, std::vector < std::vector < int > > &g, std::vector < int > &sum) {
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y] == 0) {
            dfs(y, viz, g, sum);
            sum[x] += sum[y];
        }
    }
}

inline int solve(int n, int *X, int *Y) {
    std::vector < std::pair < int, int > > v(n);
    for (int i = 0; i < n; i++)
        v[i] = {X[i], Y[i]};
    std::sort(v.begin(), v.end());

    int k = 1;
    std::vector < int > boss(n, 1);
    for (int i = 1; i < n; i++)
        if (v[i].x == v[i - 1].x && v[i].y == v[i - 1].y + 1)
            boss[i] = boss[i - 1];
        else
            boss[i] = ++k;

    std::map < std::pair < int, int > , int > mp;
    std::vector < int > sum(k + 1, 0);
    for (int i = 0; i < n; i++)
        mp[v[i]] = boss[i], sum[boss[i]]++;

    std::vector < std::vector < int > > g(k + 1);
    std::vector < int > last(k + 1, 0);
    for (int i = 0; i < n; i++) {
        int x = mp[{v[i].x - 1, v[i].y}];
        if (x && last[boss[i]] != x) {
            last[boss[i]] = x;
            g[boss[i]].push_back(x);
            g[x].push_back(boss[i]);
        }
    }

    std::vector < bool > viz(k + 1, 0);
    int rad = 1;
    dfs(rad, viz, g, sum);

    int ans = 0;
    for (int i = 1; i <= k; i++)
        ans = (ans + 1LL * sum[i] * (n - sum[i])) % MOD;
    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    return (solve(N, X, Y) + solve(N, Y, X)) % MOD;
}

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