oj.uz

Submission #1017498

# Submission time Handle Problem Language Result Execution time Memory
1017498 2024-07-09T08:24:51 Z NintsiChkhaidze Ideal city (IOI12_city) C++17
0 / 100
 1000 ms 7004 KB 
#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;
	}	
	
	ll 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.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 7004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 7004 KB Time limit exceeded
2 Halted 0 ms 0 KB -