Submission #1845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1845		kriii	Ideal city (IOI12_city)	C++98	100 / 100	69 ms	13628 KiB

city

#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct INT{
	INT(int s_, int e_, int i_){s = s_; e = e_; i = i_;}
	int s,e,i;
};

const int mod = 1000000000;
vector<int> Graph[100001],Point[100001];
vector<INT> Interval[100001];
int node,size[100001],Q[100001]; bool chk[100001];

inline bool intersect(INT a, INT b)
{
	return max(a.s,b.s) <= min(a.e,b.e);
}

inline void addEdge(int x, int y)
{
	Graph[x].push_back(y);
	Graph[y].push_back(x);
}

int cut(int N, int *X, int *Y)
{
	int i, j, k, maxx = X[0], s, e;
	for (i=1;i<N;i++){
		maxx = max(maxx,X[i]);
	}

	for (i=0;i<N;i++) Point[X[i]].push_back(Y[i]);
	for (i=0;i<=maxx;i++){
		sort(Point[i].begin(),Point[i].end());
		s = e = Point[i][0]; Point[i].push_back(0x7fffffff);
		for (j=1;j<Point[i].size();j++){
			if (++e != Point[i][j]){
				size[node] = e - s;
				Interval[i].push_back(INT(s,e,node++));
				s = e = Point[i][j];
			}
		}
	}

	for (i=0;i<maxx;i++){
		j = k = 0;
		while (j < Interval[i].size() && k < Interval[i+1].size()){
			INT p = Interval[i][j];
			INT q = Interval[i+1][k];
			
			if (intersect(p,q)){
				addEdge(p.i,q.i);
			}

			(p.e < q.e) ? j++ : k++;
		}
	}

	int head=-1, tail=-1;
	Q[++head] = 0; chk[0] = 1;
	while (tail < head){
		s = Q[++tail];
		for (i=0;i<Graph[s].size();i++){
			e = Graph[s][i];
			if (!chk[e]){
				Q[++head] = e; chk[e] = 1;
			}
		}
	}
	for (j=node-1;j>=0;j--){
		s = Q[j]; chk[s] = 0;
		for (i=0;i<Graph[s].size();i++){
			e = Graph[s][i];
			if (!chk[e]) size[s] += size[e];
		}
	}

	int res = 0;
	for (i=0;i<node;i++){
		res = (res + (long long)(N - size[i]) * size[i]) % mod;
	}
	for (i=0;i<node;i++){
		Graph[i].clear();
	}
	node = 0;

	for (i=0;i<=maxx;i++){
		Point[i].clear();
		Interval[i].clear();
	}

	return res;
}

int DistanceSum(int N, int *X, int *Y)
{
	int i, minx = X[0], miny = Y[0];
	for (i=1;i<N;i++){
		minx = min(minx,X[i]);
		miny = min(miny,Y[i]);
	}
	for (i=0;i<N;i++){
		X[i] -= minx;
		Y[i] -= miny;
	}

	return (cut(N,X,Y) + cut(N,Y,X)) % mod;
}

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