Submission #99914

#	Time	Username	Problem	Language	Result	Execution time	Memory
99914		jhnah917	Ideal city (IOI12_city)	C++14	68 / 100	292 ms	24956 KiB

city

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int mod = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int uf[101010];
int size[101010];
int chk[101010];
int n;
set<int> g[101010];

int find(int v){
	return uf[v] == v ? v : uf[v] = find(uf[v]);
}

void merge(int u, int v){
	u = find(u), v = find(v);
	if(u^v) uf[u] = v;
}

void dfs(int now, int prv, int &dist){ //거리 구하기 
	for(auto nxt : g[now]){
		if(nxt^prv && !chk[nxt]){
			chk[nxt] = 1;
			dfs(nxt, now, dist);
			size[now] += size[nxt];
		}
	}
	ll tmp = (ll)size[now] * (ll)(n - size[now]);
	tmp %= mod;
	dist += tmp; dist %= mod;
}

int getDist(){
	int ret = 0;
	chk[find(0)+1] = 1;
	for(int i=0; i<n; i++) size[find(i)+1]++;
	dfs(find(0)+1, 0, ret);
	return ret;
}

void makeTree(vector<p> &v){
	//init
	map<p, int> mp;
	sort(v.begin(), v.end());
	memset(size, 0, sizeof size);
	memset(chk, 0, sizeof chk);
	for(int i=0; i<n; i++) g[i].clear();
	for(int i=0; i<=n+1; i++) uf[i] = i;
	
	//union
	for(int i=0; i<n-1; i++){
		if(v[i].x == v[i+1].x && v[i].y+1 == v[i+1].y){
			merge(i, i+1);
		}
	}
	for(int i=0; i<n; i++){
		mp[{v[i].x, v[i].y}] = find(i)+1;
	}
	
	//make
	for(int i=0; i<n; i++){
		int x = v[i].x, y = v[i].y;
		for(int k=0; k<4; k++){
			int xx = x + dx[k], yy = y + dy[k];
			int nxt = mp[{xx, yy}];
			if(nxt != 0 && find(i)+1 != nxt) g[find(i)+1].insert(nxt);
		}
	}
}

int DistanceSum(int N, int *X, int *Y){
	n = N;
	int ret = 0;
	vector<p> v(n);
	for(int i=0; i<n; i++){
		v[i] = {X[i], Y[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	
	for(int i=0; i<n; i++){
		v[i] = {Y[i], X[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	ret %= mod;
	return ret;
}

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