Submission #17168

#	Time	Username	Problem	Language	Result	Execution time	Memory
17168		murat	Ideal city (IOI12_city)	C++98	100 / 100	114 ms	16884 KiB

city

#include<bits/stdc++.h>

using namespace std;

#define type(x) __typeof(x.begin())
#define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++)
#define mp make_pair
#define pb push_back
#define nd second
#define st first

const int N = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9;

typedef pair< int , int > pii;

int n, m, x, y, z, t, size[N], root[N];
map< int , vector< int > > D, Y;
vector< int > v[N];
int sum[N];

int findset(int x) { return root[x] = root[x] == x ? x : findset(root[x]); }

int merge(int x, int y) {
    v[x].pb(y);
    v[y].pb(x);
}

int dfs(int node, int root = 0) {
    int all = 0;
    foreach(it, v[node]) {
        if(*it == root) continue;
        all = (all + dfs(*it, node)) % mod;
        sum[node] += sum[*it];
    }
    return (all + (long long) sum[node] * (n - sum[node])) % mod;
}

int solve() {
    map< pii , int > dp;
    int all = 0, ty = -5;
    int S = 0;
    vector< pair< pii , int > > tt;
    foreach(it, D) {
        vector< int > &v = (it->nd);
        vector< pair< pii , int > > l;
        int yy = it->st;
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++) {
            int oo = i;
            while(i + 1 < v.size() && v[i] + 1 == v[i+1])
                i++;
            l.pb(mp(mp(v[oo], v[i]), ++S));
            ::v[S].clear();
            sum[S] = l.back().st.nd - l.back().st.st + 1;
        }
        if(ty + 1 == yy) {
            int j = 0;
            foreach(it, l) {
                while(tt[j].st.nd < it->st.st && j < tt.size()) {
                    j++;
                }
                while(tt[j].st.st <= it->st.nd && j < tt.size()) {
                    merge(tt[j].nd, it->nd);
                    j++;
                } if(j) j--;
            }
        }
        foreach(it, l) {
            int sz = size[findset(it->nd)];
            all = (all +  sz * (long long) (n - sz));
        }
        tt = l;
        ty = yy;
    }

    return dfs(1);
}

int DistanceSum(int N, int *X, int *Y) {

    n = N;
    for(int i = 0; i < N; i++) {
        int x = X[i], y = Y[i];
        ::D[y].pb(x);
        ::Y[x].pb(y);
    }

    int ans = solve();

    ::D.clear(); ::Y.clear();

    for(int i = 0; i < N; i++) {
        int y = X[i], x = Y[i];
        ::D[y].pb(x);
        ::Y[x].pb(y);
    }

    ans = (ans + solve()) % mod;

    return ans;

}

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