oj.uz

Submission #393601

# Submission time Handle Problem Language Result Execution time Memory
393601 2021-04-24T05:20:31 Z Hazem Ideal city (IOI12_city) C++14
55 / 100
 552 ms 10572 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9656 KB Output is correct
6 Correct 9 ms 9704 KB Output is correct
7 Correct 10 ms 9672 KB Output is correct
8 Correct 9 ms 9676 KB Output is correct
9 Correct 10 ms 9676 KB Output is correct
10 Correct 11 ms 9676 KB Output is correct
11 Correct 11 ms 9748 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9932 KB Output is correct
2 Correct 104 ms 9932 KB Output is correct
3 Correct 200 ms 10060 KB Output is correct
4 Correct 244 ms 10060 KB Output is correct
5 Correct 375 ms 10188 KB Output is correct
6 Correct 454 ms 10256 KB Output is correct
7 Correct 319 ms 10308 KB Output is correct
8 Correct 443 ms 10188 KB Output is correct
9 Correct 551 ms 10160 KB Output is correct
10 Correct 552 ms 10188 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9804 KB Output is correct
2 Correct 12 ms 9908 KB Output is correct
3 Correct 21 ms 10120 KB Output is correct
4 Correct 20 ms 10164 KB Output is correct
5 Correct 38 ms 10444 KB Output is correct
6 Correct 39 ms 10464 KB Output is correct
7 Correct 38 ms 10528 KB Output is correct
8 Correct 39 ms 10572 KB Output is correct
9 Correct 36 ms 10472 KB Output is correct
10 Correct 35 ms 10492 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9804 KB Output isn't correct
2 Halted 0 ms 0 KB -