oj.uz

Submission #1017499

# Submission time Handle Problem Language Result Execution time Memory
1017499 2024-07-09T08:26:47 Z NintsiChkhaidze Ideal city (IOI12_city) C++17
32 / 100
 1000 ms 7080 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#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 ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5720 KB Output is correct
4 Correct 3 ms 5720 KB Output is correct
5 Correct 3 ms 5732 KB Output is correct
6 Correct 6 ms 5936 KB Output is correct
7 Correct 6 ms 5724 KB Output is correct
8 Correct 5 ms 5720 KB Output is correct
9 Correct 5 ms 5936 KB Output is correct
10 Correct 6 ms 5724 KB Output is correct
11 Correct 8 ms 5720 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5976 KB Output is correct
2 Correct 91 ms 5976 KB Output is correct
3 Correct 245 ms 5980 KB Output is correct
4 Correct 208 ms 6000 KB Output is correct
5 Correct 455 ms 5980 KB Output is correct
6 Correct 368 ms 6036 KB Output is correct
7 Correct 365 ms 6040 KB Output is correct
8 Correct 308 ms 6228 KB Output is correct
9 Correct 355 ms 5980 KB Output is correct
10 Correct 362 ms 5980 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 7000 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 1050 ms 7080 KB Time limit exceeded
2 Halted 0 ms 0 KB -