Submission #287905

#	Time	Username	Problem	Language	Result	Execution time	Memory
287905		emanIaicepsa	이상적인 도시 (IOI12_city)	C++14	32 / 100	1090 ms	6948 KiB

city

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<ll>
#define fi first
#define se second
#define pb emplace_back
const ll mod = 1000000000;
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};
map<pii,int> vis;
ll dis[100005];
vi E[100005];

ll BFS(int x){
	ll ans = 0;
	queue<int> q;
	q.push(x);
	dis[x] = 0;
	while(!q.empty()){
		int nd = q.front(); q.pop();
		for(auto &i:E[nd]){
			if(dis[i] != -1) continue;
			dis[i] = dis[nd]+1;
			if(i > x) ans += dis[i];
			ans %= mod;
			q.push(i);
		}
	}
	return ans;
}

int DistanceSum(int N, int *X, int *Y) {
	for(int i=0;i<N;i++){
		vis[{X[i],Y[i]}] = i+1;
		for(int j=0;j<4;j++){
			int nx = X[i] + dx[j], ny = Y[i] + dy[j];
			int id = vis[{nx,ny}];
			if(id){
				E[i+1].pb(id);
				E[id].pb(i+1);
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=N;i++){
		memset(dis, -1, sizeof(dis));
		ans += BFS(i);
		ans %= mod;
	}
	return ans;
}

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