Submission #382826

#	Time	Username	Problem	Language	Result	Execution time	Memory
382826		alishahali1382	Ideal city (IOI12_city)	C++14	100 / 100	78 ms	14188 KiB

city

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans;
int n, m, k, u, v, x, y, t, a, b;
int par[MAXN], sz[MAXN];
vector<pii> v1[MAXN], v2[MAXN];
vector<int> G[MAXN];

int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
void join(int x, int y){
//	debug2(x, y)
	x=get(x);
	y=get(y);
	if (x==y) return ;
	if (x<y) swap(x, y);
	par[x]=y;
	sz[y]+=sz[x];
}
int dfs(int node, int par){
//	debug2(node, sz[node])
	for (int v:G[node]) if (v!=par) sz[node]+=dfs(v, node);
//	debug2(node, sz[node])
	ans+=1ll*sz[node]*(n-sz[node]);
	return sz[node];
}
void Solve(){
	for (int i=0; i<MAXN; i++) for (int j=1; j<SZ(v1[i]); j++)
		if (v1[i][j].first-v1[i][j-1].first==1) join(v1[i][j].second, v1[i][j-1].second);
	for (int i=1; i<MAXN; i++){
		int j=0;
		for (int jj=0; jj<SZ(v1[i-1]); jj++){
			pii p=v1[i-1][jj];
			while (j<SZ(v1[i]) && p.first>v1[i][j].first) j++;
			if (j<SZ(v1[i]) && p.first==v1[i][j].first){
				if (jj && j && v1[i-1][jj-1].first==v1[i][j-1].first && v1[i-1][jj-1].first==p.first-1) continue ;
//				debug2(p.second, v1[i][j].second)
				G[get(p.second)].pb(get(v1[i][j].second));
				G[get(v1[i][j].second)].pb(get(p.second));
			}
		}
	}
	dfs(0, 0);
}

int DistanceSum(int nn, int *X, int *Y){
	n=nn;
	x=*min_element(X, X+n);
	y=*min_element(Y, Y+n);
	for (int i=0; i<n; i++){
		X[i]-=x;
		Y[i]-=y;
		// :)
		v1[X[i]].pb({Y[i], i});
		v2[Y[i]].pb({X[i], i});
		par[i]=i;
		sz[i]=1;
	}
	for (int i=0; i<MAXN; i++){
		sort(all(v1[i]));
		sort(all(v2[i]));
	}
	Solve();
//	debug(ans)	
	
	for (int i=0; i<MAXN; i++) v1[i].swap(v2[i]);
	for (int i=0; i<n; i++){
		swap(X[i], Y[i]);
		par[i]=i;
		sz[i]=1;
		G[i].clear();
	}
	Solve();
//	debug(ans)
	return ans%1000000000;
}

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