Submission #24234

#	Time	Username	Problem	Language	Result	Execution time	Memory
24234		Hiasat	Ideal city (IOI12_city)	C++14	32 / 100	983 ms	20312 KiB

city

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

pii p[100001],mv[4] = {make_pair(0,-1),make_pair(0,1),make_pair(-1,0),make_pair(1,0)};

int dsu[100001],n,sz[100001],dp[100001];
map< pii , int > mp,edge;

vector<int> adj[100001];

ll fn = 0;

int find(int u){
	return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}

void pre(int u , int p){
	dp[u] = sz[u];
	for (int i = 0; i < adj[u].size(); ++i){
		int v = adj[u][i];
		if(v == p)
			continue;
		pre(v,u);
		dp[u] += dp[v];
	}
}
void dfs(int u , int p){
	if(p != -1){
		fn += dp[u] * (n-dp[u]);
	}
	for (int i = 0; i < adj[u].size(); ++i){
		int v = adj[u][i];
		if(v == p)
			continue;
		dfs(v,u);
	}
}
void solve(){
	edge.clear();
	for (int i = 0; i < n; ++i){
		adj[i].clear();
		dsu[i] = i;
		sz[i] = 0;
	}
	for (int i = 0; i < n; ++i){
		for(int j = 0 ; j < 2 ; j++){
			int newX = mv[j].first + p[i].first;
			int newY = mv[j].second + p[i].second;
			if(mp.find(make_pair(newX,newY)) != mp.end()){
				dsu[find(i)] = find(mp[make_pair(newX,newY)]);
			}
		}
	}
	for (int i = 0; i < n; ++i){
		sz[find(i)]++;
		for(int j = 2 ; j < 4 ; j++){
			int newX = mv[j].first + p[i].first;
			int newY = mv[j].second + p[i].second;
			if(mp.find(make_pair(newX,newY)) != mp.end()){
				int idx = mp[make_pair(newX,newY)];
				if(edge.find(make_pair(find(i),find(idx))) == edge.end()){
					edge[make_pair(find(i),find(idx))] = edge[make_pair(find(idx),find(i))] = 1;
					adj[find(i)].push_back(find(idx));
					adj[find(idx)].push_back(find(i));
				}
			}
		}
	}
	for (int i = 0; i < n; ++i){
		if(find(i) == i){
			pre(i,-1); 
			dfs(i,-1);
			break;
		}
	}
}
int DistanceSum(int N, int *X, int *Y) {
	n = N;
	for (int i = 0; i < N; ++i){
		p[i] = make_pair(X[i],Y[i]);
		mp[p[i]] = i;
	}
	solve();
	swap(mv[0],mv[2]);
	swap(mv[1],mv[3]);
	solve();

	return fn%1000000000;
}

Compilation message (stderr)

city.cpp: In function 'void pre(int, int)':
city.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i){
                    ^
city.cpp: In function 'void dfs(int, int)':
city.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i){
                    ^

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