Submission #117363

#	Time	Username	Problem	Language	Result	Execution time	Memory
117363		someone_aa	Ideal city (IOI12_city)	C++17	100 / 100	595 ms	45304 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
const ll mod = 1e9;
ll result;

class tree {
public:
    int usize[maxn], uparent[maxn], n;
    int value[maxn];
    ll total_sum, sbtsize[maxn];
    vector<int>g[maxn];

    void init(int _n) {
        n = _n;
        for(int i=1;i<=n;i++) {
            usize[i] = 1;
            uparent[i] = i;
        }
    }
    int ufind(int x) {
        while(x != uparent[x]) {
            x = uparent[x];
        }
        return x;
    }
    void add_edge(int x, int y) {
        g[x].pb(y);
        g[y].pb(x);
    }
    void unite(int x, int y) {
        int _x = x, _y = y;
        x = ufind(x);
        y = ufind(y);

        if(x == y) return;
        add_edge(_x, _y);

        if(usize[x] > usize[y]) {
            uparent[y] = x;
            usize[x] += usize[y];
        }
        else {
            uparent[x] = y;
            usize[y] += usize[x];
        }
    }
    void init_dfs() {
        for(int i=1;i<=n;i++) {
            total_sum += value[i];
        }
    }
    void dfs(int node, int p) {
        sbtsize[node] = value[node];
        for(int i:g[node]) {
            if(i != p) {
                dfs(i, node);
                result += sbtsize[i] * (total_sum - sbtsize[i]);
                result %= mod;
                sbtsize[node] += sbtsize[i];
            }
        }
    }
}t1, t2;

map<pair<int,int>, int> rcomp, ccomp;
map<pair<int,int>, bool> exist;
set<int> rs, cs;
map<int,set<int> > r, c;

int DistanceSum(int N, int *X, int *Y) {
    for(int i=0;i<N;i++) {
        rs.insert(X[i]);
        cs.insert(Y[i]);
        exist[mp(X[i], Y[i])] = true;
        r[X[i]].insert(Y[i]);
        c[Y[i]].insert(X[i]);
    }

    t1.init(N);
    t2.init(N);
    int br = 0;
    for(auto i:rs) {
        for(int j:r[i]) {
            int cx = i;
            int cy = j;

            if(!exist[mp(cx, cy-1)])
                br++;
            rcomp[mp(cx, cy)] = br;
            t1.value[br]++;

            if(exist[mp(cx-1, cy)]) {
                t1.unite(rcomp[mp(cx-1, cy)], br);
            }
        }
    }

    br = 0;
    for(auto i:cs) {
        for(int j:c[i]) {
            int cx = j;
            int cy = i;

            if(!exist[mp(cx-1, cy)])
                br++;
            ccomp[mp(cx, cy)] = br;
            t2.value[br]++;

            if(exist[mp(cx, cy-1)]) {
                t2.unite(ccomp[mp(cx, cy-1)], br);
            }
        }
    }

    t1.init_dfs();
    t2.init_dfs();
    t1.dfs(1, -1);
    t2.dfs(1, -1);
    return result;
}

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