Submission #102374

#	Time	Username	Problem	Language	Result	Execution time	Memory
102374		naoai	Ideal city (IOI12_city)	C++14	100 / 100	720 ms	15416 KiB

city

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
const int mod = 1e9;
const int nmax = 1e5;

i64 sum;
int n;
int sz[nmax + 1], comp[nmax + 1];
bool viz[nmax + 1];
vector<int> g[nmax + 1];

map<pair<int, int>, int> mp;

void dfs (int nod, pair<int, int> pos, int ind) { // componentele sunt secventele consec pe ac coloana
    if (viz[nod] == 1)
        return ;

    ++ sz[ind];
    viz[nod] = 1;
    comp[nod] = ind;

    -- pos.first;
    if (mp.find(pos) != mp.end()) {
        dfs(mp[pos], pos, ind);
    }

    pos.first += 2;
    if (mp.find(pos) != mp.end()) {
        dfs(mp[pos], pos, ind);
    }
}

void calc (int nod, int t) {
    for (auto i : g[nod]) {
        if (i != t) {
            calc(i, nod);

            sz[nod] += sz[i];
        }
    }

    sum = (sum + 1LL * sz[nod] * (n - sz[nod])) % mod;
}

int solve (int N, int *X, int *Y) {
    for (int i = 0; i < N; ++ i)
        mp[{X[i], Y[i]}] = i;

    int nrc = 0;
    for (int i = 0; i < N; ++ i) {
        if (viz[i] == 0) {
            dfs(i, {X[i], Y[i]}, ++ nrc);
        }
    }

    n = N;

    for (int i = 0; i < N; ++ i) {
        int y = Y[i] + 1;
        if (mp.find({X[i], y}) != mp.end()) {
            int u = comp[mp[{X[i], y}]];

            g[comp[i]].push_back(u);
            g[u].push_back(comp[i]);
        }
    }

    for (int i = 1; i <= nrc; ++ i) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }

    sum = 0;
    calc(1, 0);

    memset(sz, 0, sizeof(sz));
    memset(viz, 0, sizeof(viz));
    mp.clear();
    for (int i = 1; i <= nrc; ++ i) {
        g[i].clear();
    }

    return sum;
}

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

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