Submission #362963

#	Time	Username	Problem	Language	Result	Execution time	Memory
362963		Seanliu	Ideal city (IOI12_city)	C++14	32 / 100	194 ms	1004 KiB

city

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;

const int MOD = 1e9, maxN = 2326;
const long long int INF = (1LL << 31) - 2;

int mp[maxN][maxN], vis[maxN], d[maxN], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<int> que;

inline int add(int a, int b){
	return (a + b >= MOD ? a + b - MOD : a + b);
}

int DistanceSum(int N, int *X, int *Y) {
	if(N > maxN) return 0;
	int minX = INF, minY = INF;
	for(int i = 0; i < N; i++){
		minX = min(minX, X[i]);
		minY = min(minY, Y[i]);
	}
	for(int i = 0; i < N; i++){
		X[i] -= minX - 1;
		Y[i] -= minY - 1;
		mp[X[i]][Y[i]] = i + 1;
	}
	long long int ans = 0;
	for(int i = 0; i < N; i++){
		fill(d, d + N, INF);	
		fill(vis, vis + N, false);
		d[i] = 0;
		que.push(i);
		vis[i] = true;
		//cout << "i = " << i << endl;
		while(que.size()){
			int id = que.front(); que.pop();
			for(int j = 0; j < 4; j++){
				if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
					int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
					if(!vis[nid]){
						d[nid] = d[id] + 1;
						//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
						ans = add(ans, d[nid]);
						vis[nid] = true;
						que.push(nid);
					}
				}
			}
		}
	}
	return ans / 2;
}

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