oj.uz

Submission #148295

# Submission time Handle Problem Language Result Execution time Memory
148295 2019-08-31T21:59:53 Z youssefbou62 Ideal city (IOI12_city) C++14
32 / 100
 230 ms 32996 KB 
#include  <bits/stdc++.h>
// #include "city.h"
using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }

ll ans ;
int root ; 
const int N = 2e3+5; 
int visited[N] ; 
const ll mod = 1e9 ; 
int notE[N][N],x[N],y[N]; 
void bfs(int root ){
	int u = root; 
	queue<int> q; 
	q.push(u); 
	visited[u]=0; 
	int dx [][2] ={{0,-1},{0,1},{1,0},{-1,0}};
	while(!q.empty()){
		u = q.front(); 
		q.pop(); 
		// cout << visited[u]<<" " << ans <<endl; 
		if( u >= root )ans += visited[u] , ans %= mod; 
		for(int i = 0 ; i < 4 ; i++ ){
			int xx = x[u]+dx[i][0] ; 
			int yy = y[u]+dx[i][1] ; 

			if( xx >= 0 && yy >= 0 &&notE[xx][yy]!=-1&& visited[notE[xx][yy]]==-1 ){
				visited[notE[xx][yy]] = visited[u]+1; 
				q.push(notE[xx][yy]); 
			}
		}
	}
}

int DistanceSum(int N, int *X, int *Y){
	memset(notE,-1,sizeof notE); 
	for(int i = 0 ; i < N ; i++ ){
		notE[X[i]][Y[i]]=i;
		x[i] = X[i] ; 
		y[i] = Y[i] ; 
	} 
	for(int i = 0 ; i < N ; i++ ){
		memset(visited,-1,sizeof visited) ; 
		bfs(i); 
	}
	return ans; 
}
// int main(){
// 	int n ; cin >> n ; for(int i = 0 ; i < n ; i++ )cin >> x[i]>>y[i] ; cout << DistanceSum(n,x,y)<<endl; 
// }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16248 KB Output is correct
2 Correct 15 ms 16120 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Correct 15 ms 16120 KB Output is correct
6 Correct 16 ms 16120 KB Output is correct
7 Correct 16 ms 15992 KB Output is correct
8 Correct 16 ms 16120 KB Output is correct
9 Correct 16 ms 15992 KB Output is correct
10 Correct 16 ms 16120 KB Output is correct
11 Correct 16 ms 16120 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16120 KB Output is correct
2 Correct 52 ms 16120 KB Output is correct
3 Correct 126 ms 16152 KB Output is correct
4 Correct 107 ms 16120 KB Output is correct
5 Correct 219 ms 16156 KB Output is correct
6 Correct 161 ms 16120 KB Output is correct
7 Correct 230 ms 16248 KB Output is correct
8 Correct 162 ms 16248 KB Output is correct
9 Correct 152 ms 16124 KB Output is correct
10 Correct 151 ms 16248 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 32996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 32860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -