제출 #132866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132866		arthurconmy	이상적인 도시 (IOI12_city)	C++14	0 / 100	11 ms	2296 KiB

city

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2001; // 1-index that shit
const int INF=1000000000;
vector<int> adj[MAXN];
map<pair<int,int>,int> M;

int DistanceSum(int N, int *X, int *Y)
{
	for(int i=0; i<N; i++)
	{
		int x=X[i];
		int y=Y[i];
		M[make_pair(x,y)]=i+1;

		for(int x_b=-1; x_b<=1; x_b++)
		{
			for(int y_b=-1; y_b<=1; y_b++)
			{
				if(abs(x_b) + abs(y_b) != 1) continue;

				if(M[make_pair(x+x_b,y+y_b)])
				{
					int cur = M[make_pair(x+x_b,y+y_b)];
					adj[cur].push_back(i+1);
					adj[i+1].push_back(cur);
				}
			}
		}
	}

	long long ans=0;

	for(int u=1; u<=N; u++)
	{
		vector<int> dis(N+1,INF);
		dis[u]=0;

		vector<int> BFS = {u};

		while(!BFS.empty())
		{
			vector<int> new_BFS;

			for(auto v:adj[u])
			{
				if(dis[v]!=INF) continue;
				dis[v]=dis[u]+1;
				ans += dis[v];
				new_BFS.push_back(v);
			}

			BFS = new_BFS;
		}
	}

	return ans;
}

// int main()
// {
// 	#ifdef ARTHUR_LOCAL
// 		ifstream cin("input.txt");
// 	#endif

		
// }

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