oj.uz

Submission #119960

# Submission time Handle Problem Language Result Execution time Memory
119960 2019-06-22T18:35:10 Z ioilolcom Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 3660 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define x first
#define y second
#define pii pair<int,int>
typedef long long int ll;
const int N=2e4+7;
vector<pii> points;
vector<int> adj[N];
int n;
bool vis[N];
int dist[N];
map<pii,int> mp;
vector<pii> edges;
ll ans;
void bfs(int x){
	queue<int>  q;
	memset(vis,0,sizeof vis);
	memset(dist,0,sizeof dist);
	//cout<<"here"<<endl;
	q.push(x);
	dist[x]=0;
	vis[x]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int v:adj[u]) {
			if(!vis[v]) {
				vis[v]=1;
				q.push(v);
				dist[v]=dist[u]+1;
			}
		}
	}
	for(int i=0; i<n; i++) {
		ans+=dist[i];
	}
//	cout<<endl;

}


int DistanceSum(int N, int *X, int *Y)
{
	n=N;
	for(int i=0; i<n; i++) {
		points.push_back({X[i],Y[i]});
		mp[{X[i],Y[i]}]=i;
	}
	for(int i=0; i<(int)points.size(); i++) {
		for(int j=i+1; j<(int)points.size(); j++) {
			if(abs(points[i].x-points[j].x)+abs(points[i].y-points[j].y)==1) {
				adj[mp[points[i]]].push_back(mp[points[j]]);
				adj[mp[points[j]]].push_back(mp[points[i]]);
				edges.push_back({mp[points[i]],mp[points[j]]});
			}
		}
	}
	for(int i=0; i<n; i++) {
		bfs(i);
	}
	ans=ans/2;
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1024 KB Output is correct
2 Correct 30 ms 1068 KB Output is correct
3 Correct 63 ms 1132 KB Output is correct
4 Correct 65 ms 1200 KB Output is correct
5 Correct 107 ms 1244 KB Output is correct
6 Correct 112 ms 1220 KB Output is correct
7 Correct 111 ms 1220 KB Output is correct
8 Correct 111 ms 1152 KB Output is correct
9 Correct 114 ms 1220 KB Output is correct
10 Correct 109 ms 1220 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 3660 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 1067 ms 3456 KB Time limit exceeded
2 Halted 0 ms 0 KB -