Submission #318028

#	Time	Username	Problem	Language	Result	Execution time	Memory
318028		tengiz05	Ideal city (IOI12_city)	C++17	100 / 100	77 ms	11484 KiB

city

#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long ll;
const ll N = 1e5+5, mod = 1e9;
ll sz[N], c[N], n, id[N];
bool used[N];
vector<int> edges[N];
vector<pair<int, int>> p;
ll ans;
void dfs(int u){
	sz[u] = c[u];
	used[u]=true;
	for(auto v : edges[u]){
		if(!used[v]){
			dfs(v);
			sz[u] += sz[v];
		}
	}ans += sz[u]*(n-sz[u]);ans%=mod;
}
void build(){
	sort(all(p));
	int timer=0;
	for(int i=0;i<n;i++){
		int e=i;
		while(e+1<n && p[e].ff == p[e+1].ff && p[e+1].ss == p[e].ss+1)e++;
		for(int j=i;j<=e;j++){
			int x = lower_bound(all(p), make_pair(p[j].ff-1, p[j].ss))-p.begin();
			if(p[x] == make_pair(p[j].ff-1, p[j].ss)){
				edges[id[x]].push_back(timer);
				edges[timer].push_back(id[x]);
			}id[j] = timer;
		}c[timer] = e-i+1;
		timer++;
		i = e;
	}dfs(0);
	for(int i=0;i<n;i++)c[i]=0, sz[i]=0, id[i]=0;
	for(int i=0;i<=timer;i++)edges[i].clear(), used[i]=0;
}
int DistanceSum(int NN, int *X, int *Y) {
	n = NN;
	for(int i=0;i<n;i++){
		p.push_back({X[i], Y[i]});
	}build();	
	p.clear();
	for(int i=0;i<n;i++){
		p.push_back({Y[i], X[i]});
	}build();
	return (int)ans%mod;
}

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