Submission #157535

#	Time	Username	Problem	Language	Result	Execution time	Memory
157535		oolimry	Ideal city (IOI12_city)	C++14	100 / 100	447 ms	22852 KiB

city

#include <bits/stdc++.h>
using namespace std;

int n;
long long ans = 0, cnt = -1;
typedef pair<long long, long long> ii;

map<ii, bool> vis;
long long sz[100005];
long long deg[100005];
set<int> adj[100005];
queue<int> leaf;
void dfs(ii u, int p){
	if(vis.find(u) == vis.end()) return;
	if(vis[u]) return;
	ii v = u;
	cnt++;
	vector<ii> arr;
	while(vis.find(v) != vis.end()){
		vis[v] = true;
		arr.push_back(v);
		v.first++;
	}
	v = ii(u.first-1,u.second);
	while(vis.find(v) != vis.end()){
		vis[v] = true;
		arr.push_back(v);
		v.first--;
	}
	int curcnt = cnt;
	sz[curcnt] = arr.size();
	
	if(p != -1){
		adj[curcnt].insert(p);
		adj[p].insert(curcnt);
		deg[curcnt]++;
		deg[p]++;
	}
	/*
	cout << curcnt << " " << p << "\n";
	cout << cnt << ": ";
	for(int i = 0;i < arr.size();i++){
		cout << "(" << arr[i].first << ", " << arr[i].second << ") ";
	}
	cout << "\n";
	*/
	for(int i = 0;i < arr.size();i++){
		ii u = arr[i];
		dfs(ii(u.first,u.second+1),curcnt);
		dfs(ii(u.first,u.second-1),curcnt);
	}
	
}
void calculate(int *X, int *Y){
	cnt = -1;
	fill(sz,sz+n,0);
	fill(deg,deg+n,0);
	
	vis.clear();
	vector<ii> arr;
	for(int i = 0;i < n;i++){
		vis[ii(X[i],Y[i])] = false;
		adj[i].clear();
	}
	dfs(ii(X[0],Y[0]),-1);
	for(int i = 0;;i++){
		if(deg[i] == 0) break;
		if(deg[i] == 1) leaf.push(i);
	}
	
	while(true){
		int u = leaf.front();
		leaf.pop();
		if(adj[u].size() != 1) break;
		
		int v = *adj[u].begin();
		adj[v].erase(u);
		
		ans += sz[u] * (n - sz[u]);
		ans %= 1000000000ll;
		sz[v] += sz[u];
		if(adj[v].size() == 1){
			leaf.push(v);
		}
	}
}
int DistanceSum(int N, int *X, int *Y) {
	n = N;
	calculate(X,Y);
	calculate(Y,X);
	return ans % 1000000000ll;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(ii, int)':
city.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < arr.size();i++){
                ~~^~~~~~~~~~~~

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