oj.uz

Submission #698517

# Submission time Handle Problem Language Result Execution time Memory
698517 2023-02-13T16:42:11 Z arneves Ideal city (IOI12_city) C++17
32 / 100
 1000 ms 1908 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) {
	
	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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 300 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 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 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 56 ms 404 KB Output is correct
4 Correct 61 ms 396 KB Output is correct
5 Correct 101 ms 440 KB Output is correct
6 Correct 107 ms 444 KB Output is correct
7 Correct 105 ms 444 KB Output is correct
8 Correct 109 ms 432 KB Output is correct
9 Correct 108 ms 340 KB Output is correct
10 Correct 105 ms 340 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 1756 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 1076 ms 1908 KB Time limit exceeded
2 Halted 0 ms 0 KB -