Submission #698517

#	Time	Username	Problem	Language	Result	Execution time	Memory
698517		arneves	Ideal city (IOI12_city)	C++17	32 / 100	1083 ms	1908 KiB

city

/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
		   .      .           .      .           .      .    	
		   _\/  \/_           _\/  \/_           _\/  \/_    	
			_\/\/_             _\/\/_             _\/\/_     	
		_\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
		 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
			_/\/\_             _/\/\_             _/\/\_     	
			/\  /\             /\  /\             /\  /\     	
		   '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

vector<int> dist(int s, vector<vector<int> > &adj){
	int n=adj.size();
	queue<int> q;
	q.push(s);
	vector<int> dist(n, -1);
	dist[s]=0;
	
	while(!q.empty()){
		int v=q.front();
		q.pop();
		
		for(int u: adj[v]){
			if(dist[u]==-1){
				q.push(u);
				dist[u]=dist[v]+1;
			}
		}
	}
	
	return dist;
}

int DistanceSum(int N, int *X, int *Y) {
	
	int ans=0;
	
	vector<vector<int> > adj(N, vector<int>());
	
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			if((abs(X[i]-X[j])+abs(Y[i]-Y[j]))==1){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	
	for(int i=0; i<N; i++){
		
		vector<int> d=dist(i, adj);
		
		for(int j=i+1; j<N; j++){
			ans+=d[j];
			if(ans>=1000'000'000) ans-=1000'000'000;
		}
	}
	
	
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45