Submission #119960

#	Time	Username	Problem	Language	Result	Execution time	Memory
119960		ioilolcom	Ideal city (IOI12_city)	C++14	32 / 100	1067 ms	3660 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define x first
#define y second
#define pii pair<int,int>
typedef long long int ll;
const int N=2e4+7;
vector<pii> points;
vector<int> adj[N];
int n;
bool vis[N];
int dist[N];
map<pii,int> mp;
vector<pii> edges;
ll ans;
void bfs(int x){
	queue<int>  q;
	memset(vis,0,sizeof vis);
	memset(dist,0,sizeof dist);
	//cout<<"here"<<endl;
	q.push(x);
	dist[x]=0;
	vis[x]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int v:adj[u]) {
			if(!vis[v]) {
				vis[v]=1;
				q.push(v);
				dist[v]=dist[u]+1;
			}
		}
	}
	for(int i=0; i<n; i++) {
		ans+=dist[i];
	}
//	cout<<endl;

}


int DistanceSum(int N, int *X, int *Y)
{
	n=N;
	for(int i=0; i<n; i++) {
		points.push_back({X[i],Y[i]});
		mp[{X[i],Y[i]}]=i;
	}
	for(int i=0; i<(int)points.size(); i++) {
		for(int j=i+1; j<(int)points.size(); j++) {
			if(abs(points[i].x-points[j].x)+abs(points[i].y-points[j].y)==1) {
				adj[mp[points[i]]].push_back(mp[points[j]]);
				adj[mp[points[j]]].push_back(mp[points[i]]);
				edges.push_back({mp[points[i]],mp[points[j]]});
			}
		}
	}
	for(int i=0; i<n; i++) {
		bfs(i);
	}
	ans=ans/2;
	return ans;
}

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