Submission #383630

#	Time	Username	Problem	Language	Result	Execution time	Memory
383630		alireza_kaviani	Ideal city (IOI12_city)	C++11	100 / 100	102 ms	17256 KiB

city

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X				first
#define Y				second

const int MAXN = 2e5 + 10;
const ll INF = 1e18;
const ll MOD = 1e9;

ll n , par[MAXN] , sz[MAXN] , Sz[MAXN] , Par[MAXN];
ll ans;
vector<int> adj[MAXN];
vector<pii> vec;

int getInd(int x , int y){
	int ind = lower_bound(vec.begin() , vec.end() , pii(x , y)) - vec.begin();
	if(ind == n || vec[ind] != pii(x , y))	return -1;
	return ind;
}

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v;
	sz[v] += sz[u];
}

void DFS(int v , int p = -1){
	for(int u : adj[v]){
		if(u == p)	continue;
		DFS(u , v);
		Sz[v] += Sz[u];
	}
	ans += Sz[v] * (n - Sz[v]);
}

void solve(){
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	sort(vec.begin() , vec.end());
	for(int i = 0 ; i < n ; i++){
		adj[i].clear();
		int x = vec[i].X , y = vec[i].Y;
		int ind = getInd(x , y - 1);
		if(ind == -1)	continue;
		Union(i , ind);
	}
	for(int i = 0 ; i < MAXN ; i++)	Sz[i] = sz[i] , Par[i] = Find(i);
	for(int i = 0 ; i < n ; i++){
		int x = vec[i].X , y = vec[i].Y;
		int ind = getInd(x - 1 , y);
		if(ind == -1)	continue;
		if(Find(ind) == Find(i))	continue;
		adj[Par[ind]].push_back(Par[i]);
		adj[Par[i]].push_back(Par[ind]);
		Union(i , ind);
	}
	DFS(Find(0));
}

ll DistanceSum(int N, int *X, int *Y) {
	n = N;
	ll mnx = INF , mny = INF;
	for(int i = 0 ; i < N ; i++){
		mnx = min(mnx , (ll)X[i]);
		mny = min(mny , (ll)Y[i]);
	}
	for(int i = 0 ; i < N ; i++){
		X[i] -= mnx; Y[i] -= mny;
	}
	for(int i = 0 ; i < N ; i++)	vec.push_back({X[i] , Y[i]});
	solve(); vec = {};
	for(int i = 0 ; i < N ; i++)	vec.push_back({Y[i] , X[i]});
	solve();
	return ans % MOD;
}

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