제출 #1017495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017495		NintsiChkhaidze	이상적인 도시 (IOI12_city)	C++17	0 / 100	1102 ms	7004 KiB

city

#define ll long long
#define f first
#define s second
#include <bits/stdc++.h>
#define pii pair <int,int>
using namespace std;

const int M = 1e5 + 5,mod = 1000000000;
int n,dist[M];
vector <pii> neighbours = {{0,1}, {1,0}, {0,-1}, {-1,0} };
unordered_map <int,int> mp[100005];

int DistanceSum(int N, int *X, int *Y) {
	
	n = N;
	for (int i=0;i<n;i++){
		int x=X[i],y=Y[i];
		mp[x][y] = i;
	}	
	
	int ans = 0;
	for (int i=0;i<n;i++){
		priority_queue <pair <int,pii> > pq;
		for (int j=0;j<n;j++)
			dist[j] = 1e9;
		dist[i]=0;
		pq.push({0,{X[i],Y[i]}});
		
		while (pq.size()){
			int D = -pq.top().f;
			int x = pq.top().s.f;
			int y = pq.top().s.s;
			pq.pop();
			if (dist[mp[x][y]] != D) continue;
			
			for (auto [dx,dy]: neighbours){
				int xx = dx+x,yy=dy+y;
				if (xx >= 0 && mp[xx].find(yy) != mp[xx].end()){
					int to = mp[xx][yy];
					if (dist[to] > D + 1){
						dist[to] = D + 1;
						pq.push({-D-1,{xx,yy}});
					}
				}
			}
		}
		
		for (int j=i+1;j<n;j++){
			ans+=dist[j],ans %= mod;
		}
	}
	return 0;
}

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