Submission #577161

#	Time	Username	Problem	Language	Result	Execution time	Memory
577161		WongChun1234	Ideal city (IOI12_city)	C++14	11 / 100	1090 ms	4412 KiB

city

//#include"grader.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1000000000;
const bool DEBUG=0;
int n,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
ll ans;
pair<int,int> coord[N];
map<pair<int,int>,int> hv,vis;
queue<pair<pair<int,int>,int>> bfs;
int DistanceSum(int _N, int *x, int *y) {
	n=_N;
	for (int i=0;i<n;i++) coord[i]={x[i],y[i]};
	sort(coord,coord+n);
	for (int i=0;i<n;i++){
		hv[coord[i]]=i+1;
	}
	for (int i=0;i<n;i++){
		vis.clear();
		while (bfs.size()) bfs.pop();
		bfs.push({coord[i],0});
		vis[coord[i]]=1;
		while (bfs.size()){
			auto curr=bfs.front().first;
			int cdist=bfs.front().second;
			bfs.pop();
			for (int i=0;i<4;i++){
				if (!hv[{curr.first+dx[i],curr.second+dy[i]}]) continue;
				if (vis[{curr.first+dx[i],curr.second+dy[i]}]) continue;
				ans+=cdist+1;
				ans%=MOD;
				vis[{curr.first+dx[i],curr.second+dy[i]}]=1;
				bfs.push({{curr.first+dx[i],curr.second+dy[i]},cdist+1});
			}
		}
	}
	return ans/2;
}

/*
6
1 1
2 1
2 3
3 1
3 2
3 3
*/

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