Submission #289943

#	Time	Username	Problem	Language	Result	Execution time	Memory
289943		ToMmyDong	Ideal city (IOI12_city)	C++11	100 / 100	504 ms	19064 KiB

city

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(), i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& __printRng (ostream& os, IT bg, IT ed) {
    for (IT it=bg;it!=ed;it++) {
        if (it == bg) os << "{" << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T> &vec) {
    return __printRng(os, ALL(vec));
}
template<typename T> ostream& operator << (ostream& os, const set<T> &vec) {
    return __printRng(os, ALL(vec));
}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S> &pa) {
    return os << "{" << pa.X << "," << pa.Y << "}";
}
#else
#define debug(...)
#endif

const int MAXN = 100083;
const int MOD = 1000000000;

int add (int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}

int sub (int x, int y) {
    x -= y;
    return x < 0 ? x + MOD : x;
}

int mul (int x, int y) {
    return ll(x) * y % MOD;
}

map<pii, int> id;
int djs[MAXN], sz[MAXN];
int fnd (int x) {
    return djs[x] == x ? x : djs[x] = fnd(djs[x]);
}

void mrg (int x, int y) {
    x = fnd(x), y = fnd(y);
    if (x == y) return;
    djs[x] = y;
    sz[y] += sz[x];
}

set<int> edge[MAXN];

int ssum[MAXN], N;
int dfs (int nd, int par) {
    ssum[nd] = sz[nd];
    int res = 0;
    for (int v : edge[nd]) {
        if (v != par) {
            res = add(res, dfs(v, nd));
            ssum[nd] += ssum[v];
            debug(nd, v, ssum[v]);
            res = add(res, mul(ssum[v], N-ssum[v]));
        }
    }
    debug(nd, res, sz[nd]);
    return res;
}
int oneDirection (int n, int *x, int *y) {
    N = n;
    id.clear();
    for (int i=0; i<n; i++) djs[i] = i, sz[i] = 1;
    for (int i=0; i<n; i++) edge[i].clear(); 
    for (int i=0; i<n; i++) id[pii(x[i], y[i])] = i;

    for (int i=0; i<n; i++) {
        if (id.count({x[i]+1, y[i]})) {
            mrg(i, id[pii(x[i]+1, y[i])]);
        }
    }

    for (int i=0; i<n; i++) {
        if (id.count({x[i], y[i]+1})) {
            int uid = fnd(id[pii(x[i], y[i]+1)]);
            int vid = fnd(i);
            edge[vid].insert(uid);
            edge[uid].insert(vid);
        }
    }

    for (int i=0; i<n; i++) {
        debug(edge[i]);
        debug(sz[i]);
    }

    for (int i=0; i<n; i++) {
        if (fnd(i) == i) {
            return dfs(i, -1);
        }
    }
    return -1;
}

int DistanceSum(int n, int *x, int *y) {
    return add(oneDirection(n, x, y), oneDirection(n, y, x));
}

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