oj.uz

Submission #1847

# Submission time Handle Problem Language Result Execution time Memory
1847 2013-07-18T13:08:39 Z kriii Ideal city (IOI12_city) C++
100 / 100
 68 ms 13628 KB 
#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=0;i<N;i++){
		maxx = max(maxx,X[i]);
		Point[X[i]].push_back(Y[i]);
	}

	for (i=0;i<=maxx;i++){
		sort(Point[i].begin(),Point[i].end());
		Point[i].push_back(0x7fffffff);

		s = e = Point[i][0];
		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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8848 KB Output is correct
2 Correct 2 ms 8848 KB Output is correct
3 Correct 0 ms 8848 KB Output is correct
4 Correct 0 ms 8980 KB Output is correct
5 Correct 0 ms 8980 KB Output is correct
6 Correct 0 ms 8980 KB Output is correct
7 Correct 1 ms 8980 KB Output is correct
8 Correct 1 ms 8980 KB Output is correct
9 Correct 0 ms 8980 KB Output is correct
10 Correct 1 ms 8980 KB Output is correct
11 Correct 1 ms 8980 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8980 KB Output is correct
2 Correct 1 ms 8980 KB Output is correct
3 Correct 1 ms 8980 KB Output is correct
4 Correct 1 ms 8980 KB Output is correct
5 Correct 2 ms 8984 KB Output is correct
6 Correct 0 ms 8984 KB Output is correct
7 Correct 3 ms 8984 KB Output is correct
8 Correct 2 ms 8984 KB Output is correct
9 Correct 1 ms 8984 KB Output is correct
10 Correct 1 ms 8984 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9316 KB Output is correct
2 Correct 8 ms 9316 KB Output is correct
3 Correct 19 ms 9636 KB Output is correct
4 Correct 24 ms 10032 KB Output is correct
5 Correct 42 ms 10424 KB Output is correct
6 Correct 36 ms 11088 KB Output is correct
7 Correct 38 ms 10820 KB Output is correct
8 Correct 34 ms 10424 KB Output is correct
9 Correct 43 ms 10980 KB Output is correct
10 Correct 68 ms 13628 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9712 KB Output is correct
2 Correct 12 ms 9580 KB Output is correct
3 Correct 34 ms 10824 KB Output is correct
4 Correct 24 ms 10428 KB Output is correct
5 Correct 63 ms 12800 KB Output is correct
6 Correct 39 ms 11216 KB Output is correct
7 Correct 51 ms 12536 KB Output is correct
8 Correct 53 ms 11612 KB Output is correct
9 Correct 40 ms 10952 KB Output is correct
10 Correct 37 ms 11084 KB Output is correct