Submission #393601

#	Time	Username	Problem	Language	Result	Execution time	Memory
393601		Hazem	Ideal city (IOI12_city)	C++14	55 / 100	552 ms	10572 KiB

city

#include <bits/stdc++.h>
//#include "grader.h"

using namespace std;
 
#define S second
#define F first
#define LL long long 
 
const int N1 = 4e5+10;
const LL MOD = 1e9;
const LL LINF = 1e18;
const LL INF = 1e9;

int x[] = {1,-1,0,0};
int y[] = {0,0,1,-1};

vector<int>adj[N1];
map<pair<int,int>,int>mp,vis1;
int cnt = 1,n;
int dis[N1],vis[N1];

void dfs(int i,int j){

	if(vis1[{i,j}])return ;
	vis1[{i,j}] = 1;

	mp[{i,j}] = cnt++;

	for(int k=0;k<4;k++){
		int i1 = i+x[k],j1 = j+y[k];
		if(mp[{i1,j1}])dfs(i1,j1),adj[mp[{i,j}]].push_back(mp[{i1,j1}]);
	}
}

LL dijikstra(int st){

	LL ret = 0;
	for(int i=1;i<=n;i++)
		dis[i] = INF,vis[i] = 0;

	dis[st] = 0;
	priority_queue<pair<int,int>>que;
	que.push({0,st});

	while(!que.empty()){
		int u = que.top().S;
		que.pop();

		if(vis[u])continue;
		vis[u] = 1;

		if(u>=st)
			ret = (ret+dis[u])%MOD;
		for(auto x:adj[u])
			if(!vis[x])
				dis[x] = min(dis[x],dis[u]+1),que.push({-dis[x],x});
	}
	return ret;
}

int DistanceSum(int N, int *X, int *Y) {

	n = N;
	LL ret = 0;

	if(n>2000){
	sort(X,X+n);
	sort(Y,Y+n);

	for(LL i=0;i<n;i++){
		ret = (ret+X[i]*i+Y[i]*i)%MOD;
		ret = ((ret-X[i]*(n-i-1)-Y[i]*(n-i-1))%MOD+MOD)%MOD;
	}
	}

	else {
		for(int i=0;i<n;i++)
		mp[{X[i],Y[i]}] = 1;
 
	dfs(X[0],Y[0]);
 
	for(int i=1;i<=n;i++)
		ret = (ret+dijikstra(i))%MOD;
	}

	return ret;
}

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