oj.uz

Submission #287905

# Submission time Handle Problem Language Result Execution time Memory
287905 2020-09-01T06:19:14 Z emanIaicepsa Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 6948 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<ll>
#define fi first
#define se second
#define pb emplace_back
const ll mod = 1000000000;
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};
map<pii,int> vis;
ll dis[100005];
vi E[100005];

ll BFS(int x){
	ll ans = 0;
	queue<int> q;
	q.push(x);
	dis[x] = 0;
	while(!q.empty()){
		int nd = q.front(); q.pop();
		for(auto &i:E[nd]){
			if(dis[i] != -1) continue;
			dis[i] = dis[nd]+1;
			if(i > x) ans += dis[i];
			ans %= mod;
			q.push(i);
		}
	}
	return ans;
}

int DistanceSum(int N, int *X, int *Y) {
	for(int i=0;i<N;i++){
		vis[{X[i],Y[i]}] = i+1;
		for(int j=0;j<4;j++){
			int nx = X[i] + dx[j], ny = Y[i] + dy[j];
			int id = vis[{nx,ny}];
			if(id){
				E[i+1].pb(id);
				E[id].pb(i+1);
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=N;i++){
		memset(dis, -1, sizeof(dis));
		ans += BFS(i);
		ans %= mod;
	}
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3676 KB Output is correct
2 Correct 66 ms 3704 KB Output is correct
3 Correct 119 ms 3712 KB Output is correct
4 Correct 124 ms 3712 KB Output is correct
5 Correct 195 ms 3840 KB Output is correct
6 Correct 202 ms 3832 KB Output is correct
7 Correct 200 ms 3840 KB Output is correct
8 Correct 204 ms 3712 KB Output is correct
9 Correct 199 ms 3832 KB Output is correct
10 Correct 193 ms 3712 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 6136 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 1090 ms 6948 KB Time limit exceeded
2 Halted 0 ms 0 KB -