oj.uz

Submission #132873

# Submission time Handle Problem Language Result Execution time Memory
132873 2019-07-19T21:01:27 Z arthurconmy Ideal city (IOI12_city) C++14
32 / 100
 293 ms 2296 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MAXN=2001; // 1-index that shit
const int INF=1000000000;
vector<int> adj[MAXN];
map<pair<int,int>,int> M;
 
int DistanceSum(int N, int *X_coords, int *Y_coords)
{
	for(int i=0; i<N; i++)
	{
		int x=X_coords[i];
		int y=Y_coords[i];
		M[make_pair(x,y)]=i+1;
 
		for(int x_b=-1; x_b<=1; x_b++)
		{
			for(int y_b=-1; y_b<=1; y_b++)
			{
				if(abs(x_b) + abs(y_b) != 1) continue;
 
				if(M[make_pair(x+x_b,y+y_b)])
				{
					int cur = M[make_pair(x+x_b,y+y_b)];
					adj[cur].push_back(i+1);
					adj[i+1].push_back(cur);
				}
			}
		}
	}
 
	ll ans=0;
 
	for(int u=1; u<=N; u++)
	{
		vector<int> dis(N+1,INF);
		dis[u]=0;
 
		vector<int> BFS = {u};
 
		while(!BFS.empty())
		{
			vector<int> new_BFS;
 
			for(auto w:BFS)
			{
				for(auto v:adj[w])
				{
					if(dis[v]!=INF) continue;
					dis[v]=dis[w]+1;
					ans += ll(dis[v]);
 
					// cout << u << " " << v << " " << dis[v] << endl;
 
					new_BFS.push_back(v);
				}
			}
 
			BFS = new_BFS;
		}
	}
 
	return ll(ans/2LL);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 504 KB Output is correct
2 Correct 69 ms 552 KB Output is correct
3 Correct 137 ms 668 KB Output is correct
4 Correct 159 ms 680 KB Output is correct
5 Correct 229 ms 752 KB Output is correct
6 Correct 261 ms 760 KB Output is correct
7 Correct 293 ms 888 KB Output is correct
8 Correct 268 ms 760 KB Output is correct
9 Correct 207 ms 732 KB Output is correct
10 Correct 200 ms 760 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 2168 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 11 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -