oj.uz

Submission #16323

# Submission time Handle Problem Language Result Execution time Memory
16323 2015-08-21T10:11:56 Z comet Ideal city (IOI12_city) C++
100 / 100
 108 ms 8448 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back
#define MOD 1000000000

struct pt{
	int x,y,v;
	pt(){}
	pt(int x_,int y_):x(x_),y(y_){}
	bool operator<(const pt& r)const{
		return x!=r.x?x<r.x:y<r.y;
	}
}s[100000];

mat path;
int n;
int cnt[100000];

ll dfs(int v,int p,ll &ans){
	ll ret=0;
	for(int i=0;i<path[v].size();i++){
		int u=path[v][i];
		if(u==p)continue;
		ret+=dfs(u,v,ans);
	}
	ret+=cnt[v];
	ans+=(n-ret)*ret;
	ans%=MOD;
	return ret;
}

int f(int N, int *X, int *Y) {
	n=N;
	for(int i=0;i<N;i++)s[i]=pt(X[i],Y[i]);
	sort(s,s+N);
	int sz=0;
	for(int i=0;i<N;i++){
		int p=i;
		while(s[i].x==s[i+1].x)i++;
		int v=p;
		//printf("%d %d\n",p,i);
		while(v<=i){
			while(v<i&&s[v].y+1==s[v+1].y){
				s[v].v=sz;
				v++;
			}
			s[v].v=sz;
			cnt[sz++]=s[v].y-s[p].y+1;
			p=++v;
		}
	}
	//puts("Umm...");

	path.clear();
	path.assign(sz,vec());

	for(int i=0;i<N;i++){
	 	pt* it=lower_bound(s,s+N,pt(s[i].x-1,s[i].y));
		if(it->x==s[i].x-1&&it->y==s[i].y)path[s[i].v].pb(it->v);
		it=lower_bound(s,s+N,pt(s[i].x+1,s[i].y));
		if(it->x==s[i].x+1&&it->y==s[i].y)path[s[i].v].pb(it->v);
	}

	for(int i=0;i<sz;i++){
		//printf("%d : ",i);
		sort(path[i].begin(),path[i].end());
		path[i].erase(unique(path[i].begin(),path[i].end()),path[i].end());
		//for(int j=0;j<path[i].size();j++)printf("%d ",path[i][j]);
		//puts("");
	}
	//for(int i=0;i<sz;i++)printf("%d ",cnt[i]);
	//puts("");

	ll ret=0;
	dfs(0,0,ret);
	return (int)ret;
}

int DistanceSum(int N, int *X, int *Y){
	return (f(N,X,Y)+f(N,Y,X))%MOD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3612 KB Output is correct
2 Correct 18 ms 3612 KB Output is correct
3 Correct 42 ms 4200 KB Output is correct
4 Correct 46 ms 4092 KB Output is correct
5 Correct 94 ms 5256 KB Output is correct
6 Correct 94 ms 5236 KB Output is correct
7 Correct 96 ms 5172 KB Output is correct
8 Correct 96 ms 5248 KB Output is correct
9 Correct 101 ms 5204 KB Output is correct
10 Correct 94 ms 8448 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3800 KB Output is correct
2 Correct 21 ms 3668 KB Output is correct
3 Correct 56 ms 4784 KB Output is correct
4 Correct 54 ms 4516 KB Output is correct
5 Correct 107 ms 6300 KB Output is correct
6 Correct 98 ms 5764 KB Output is correct
7 Correct 108 ms 6456 KB Output is correct
8 Correct 103 ms 5708 KB Output is correct
9 Correct 104 ms 5508 KB Output is correct
10 Correct 100 ms 5368 KB Output is correct