oj.uz

Submission #698532

# Submission time Handle Problem Language Result Execution time Memory
698532 2023-02-13T17:23:58 Z arneves Ideal city (IOI12_city) C++17
55 / 100
 115 ms 3148 KB 
/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
		   .      .           .      .           .      .    	
		   _\/  \/_           _\/  \/_           _\/  \/_    	
			_\/\/_             _\/\/_             _\/\/_     	
		_\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
		 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
			_/\/\_             _/\/\_             _/\/\_     	
			/\  /\             /\  /\             /\  /\     	
		   '      '           '      '           '      '    	
	
*/
 
#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) {
	
	long long ans=0;
	
	if(N>2000){
		
		map<int,long long> x;
		map<int,long long> y;
		
		for(int i=0; i<N; i++){
			x[X[i]]++;
			y[Y[i]]++;
		}
		
		long long somax=0;
		long long somay=0;
		
		for(auto u: x){
			ans+=(somax*(((long long) N)-somax));
			ans%=1'000'000'000;
			somax+=u.second;
		}
		
		for(auto u: y){
			ans+=(somay*(((long long) N)-somay));
			ans%=1'000'000'000;
			somay+=u.second;
		}
		
	}else{
	
		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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 340 KB Output is correct
2 Correct 26 ms 340 KB Output is correct
3 Correct 59 ms 388 KB Output is correct
4 Correct 64 ms 396 KB Output is correct
5 Correct 103 ms 424 KB Output is correct
6 Correct 110 ms 424 KB Output is correct
7 Correct 107 ms 340 KB Output is correct
8 Correct 115 ms 436 KB Output is correct
9 Correct 113 ms 428 KB Output is correct
10 Correct 106 ms 340 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 12 ms 724 KB Output is correct
4 Correct 12 ms 720 KB Output is correct
5 Correct 27 ms 1232 KB Output is correct
6 Correct 25 ms 1260 KB Output is correct
7 Correct 28 ms 1364 KB Output is correct
8 Correct 25 ms 1112 KB Output is correct
9 Correct 24 ms 1328 KB Output is correct
10 Correct 32 ms 3148 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -