Submission #562601

#	Time	Username	Problem	Language	Result	Execution time	Memory
562601		Leo121	Ideal city (IOI12_city)	C++14	100 / 100	430 ms	25736 KiB

city

#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int (a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int (a); i >= int(b); -- i)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

const int maxn = 1e5;
const int mx[4] = {0, 0, 1, -1};
const int my[4] = {1, -1, 0, 0};
map<pii, int> mapa;
set<int> aux[maxn];
vi treex[maxn];
vi treey[maxn];
int szx[maxn];
int szy[maxn];
int compx[maxn];
int compy[maxn];
int arre[maxn][4];
bool visitadox[maxn];
bool visitadoy[maxn];
ll res;
int n;
ll mod = 1e9;
void dfsx(int u, int p){
    for(auto v : treex[u]){
        if(v != p){
            dfsx(v, u);
            res += ((ll) n - (ll) szx[v]) * (ll) szx[v];
            res %= mod;
            szx[u] += szx[v];
        }
    }
}
void dfsy(int u, int p){
    for(auto v : treey[u]){
        if(v != p){
            dfsy(v, u);
            res += ((ll) n - (ll) szy[v]) * (ll) szy[v];
            res %= mod;
            szy[u] += szy[v];
        }
    }
}
void moverme(int i, int compo, int ini){
    while(ini != -1){
        if(i <= 1){
            compy[ini] = compo;
            visitadoy[ini] = 1;
        }
        else{
            compx[ini] = compo;
            visitadox[ini] = 1;
        }
        ini = arre[ini][i];
    }
}
int DistanceSum(int N, int *X, int *Y) {
    n = N;
    forn(i, 0, N - 1){
        mapa[mp(X[i], Y[i])] = i;
    }
    memset(arre, -1, sizeof(arre));
    forn(i, 0, N - 1){
        forn(j, 0, 3){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                arre[i][j] = mapa[mp(X[i] + mx[j], Y[i] + my[j])];
            }
        }
    }
    ///x
    int compox = -1, compoy = -1;
    forn(i, 0, N - 1){
        if(!visitadoy[i]){
            moverme(0, ++ compoy, i);
            moverme(1, compoy, i);
        }
        if(!visitadox[i]){
            moverme(2, ++ compox, i);
            moverme(3, compox, i);
        }
    }
    ///visitado y
    forn(i, 0, N - 1){
        forn(j, 2, 3){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                aux[compy[i]].insert(compy[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
            }
        }
    }
    forn(i, 0, compoy){
        for(auto j : aux[i]){
            treey[i].pb(j);
        }
        aux[i].clear();
    }
    forn(i, 0, N - 1){
        forn(j, 0, 1){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                aux[compx[i]].insert(compx[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
            }
        }
        szx[compx[i]] ++;
        szy[compy[i]] ++;
    }
    forn(i, 0, compox){
        for(auto j : aux[i]){
            treex[i].pb(j);
        }
        aux[i].clear();
    }
    dfsx(0, 0);
    dfsy(0, 0);
    return (int) res;
}

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