Submission #82539

#	Time	Username	Problem	Language	Result	Execution time	Memory
82539		leejseo	Ideal city (IOI12_city)	C++11	100 / 100	80 ms	21720 KiB

city

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;
typedef pair<int, int> point;

#define x first
#define y second

const lld MOD = 1000000000;

int A[100000];
point T[100000];
int B[100000];
vector<point> L[100000];
lld ans = 0;
vector<int> adj[100000];
bool chk[100000];
bool vis[100000];

int M;

void init(){
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	for (int i=0; i<100000; i++){
		L[i].clear();
		T[i] = point(0, 0);
		adj[i].clear();
	}
	memset(chk, 0, sizeof(chk));
	memset(vis, 0, sizeof(vis));
}

int dfs(int i){
	vis[i] = 1;
	int ret = 0;
	for (int j: adj[i])
		if (!vis[j])
			ret += dfs(j);
	ret += L[i].size();
	ans = (ans + 1LL*ret*(M-ret))%MOD;
	return ret;
}

void compute_dist(int N, int *X, int *Y){
	M = N;
	for (int i=0; i<N; i++){
		T[i] = point(X[i], Y[i]);
	}
	sort(T, T+N);
	L[0].push_back(T[0]);
	int tot = 0;    
	for (int i=1; i<N; i++){
		if (L[tot].back().x == T[i].x && L[tot].back().y + 1 == T[i].y)
			L[tot].push_back(T[i]);
		else
			L[++tot].push_back(T[i]);	
		B[i] = tot;
	}
	++tot;
	int s = 1, e = 1;
	for (int i=0; i<tot; i++){
		while (true){
			if (s == tot) break;
			if (L[s][0].x <= L[i][0].x) s++;
			else{ 
				if (L[i][0].x + 1 == L[s][0].x && L[s].back().y < L[i][0].y) s++;
				else break;
			}
		}
		while (true){
			if (e == tot) break;
			if (L[e][0].x <= L[i][0].x) e++;
			else{
				if (L[i][0].x + 1 == L[e][0].x && L[e][0].y <= L[i].back().y) e++;
				else break;
			}
		}
		for (int j=s; j<e; j++){
			adj[i].push_back(j);
			adj[j].push_back(i);
		}
	}
	dfs(0);
}

int DistanceSum(int N, int *X, int *Y) {
	compute_dist(N, X, Y);
	init();
	compute_dist(N, Y, X);
  return ans;

}

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