Submission #148295

#	Time	Username	Problem	Language	Result	Execution time	Memory
148295		youssefbou62	Ideal city (IOI12_city)	C++14	32 / 100	230 ms	32996 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45