Submission #382756

#	Time	Username	Problem	Language	Result	Execution time	Memory
382756		Keshi	Ideal city (IOI12_city)	C++17	100 / 100	63 ms	21792 KiB

city

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, t, ans, sz[maxn], dp[maxn];
pll a[maxn];
vector<pll> vec[maxn];
vector<ll> g[maxn];
bool vis[maxn];

void dfs(ll v){
	vis[v] = 1;
	dp[v] = sz[v];
	for(ll u : g[v]){
		if(!vis[u]){
			dfs(u);
			ans = (ans + dp[u] * (n - dp[u])) % mod;
			dp[v] += dp[u];
		}
	}
	return;
}

int DistanceSum(int _n, int *x, int *y){
	n = _n;
	ll mnx = inf;
	for(ll i = 0; i < n; i++){
		mnx = min(mnx, (ll)x[i]);
	}
	for(ll i = 0; i < n; i++){
		x[i] -= mnx;
	}
	ll mny = inf;
	for(ll i = 0; i < n; i++){
		mny = min(mny, (ll)y[i]);
	}
	for(ll i = 0; i < n; i++){
		y[i] -= mny;
	}
	for(ll i = 0; i < n; i++){
		vec[x[i]].pb(Mp(y[i], -1));
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i].empty()) break;
		sort(all(vec[i]));
		for(ll j = 0; j < Sz(vec[i]); j++){
			if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
			sz[vec[i][j].S = t]++;
		}
		t++;
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i + 1].empty()) continue;
		ll p1 = 0, p2 = 0;
		while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
			if(vec[i][p1].F == vec[i + 1][p2].F){
				g[vec[i][p1].S].pb(vec[i + 1][p2].S);
				g[vec[i + 1][p2].S].pb(vec[i][p1].S);
			}
			if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
			else p2++;
		}
	}
	dfs(0);
	t = 0;
	for(ll i = 0; i < maxn; i++){
		vis[i] = 0;
		sz[i] = 0;
		vec[i].clear();
		g[i].clear();
	}
	swap(x, y);
	for(ll i = 0; i < n; i++){
		vec[x[i]].pb(Mp(y[i], -1));
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i].empty()) break;
		sort(all(vec[i]));
		for(ll j = 0; j < Sz(vec[i]); j++){
			if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
			sz[vec[i][j].S = t]++;
		}
		t++;
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i + 1].empty()) continue;
		ll p1 = 0, p2 = 0;
		while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
			if(vec[i][p1].F == vec[i + 1][p2].F){
				g[vec[i][p1].S].pb(vec[i + 1][p2].S);
				g[vec[i + 1][p2].S].pb(vec[i][p1].S);
			}
			if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
			else p2++;
		}
	}
	dfs(0);
	return ans;
}

/*int main(){
    fast_io;
    
    int n, x[100], y[100];
    cin >> n;
    for(ll i = 0; i < n; i++){
    	cin >> x[i] >> y[i];
	}
	cout << DistanceSum(n, x, y);
 
    return 0;
}*/

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