Submission #1013157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013157		jcelin	Ideal city (IOI12_city)	C++14	100 / 100	124 ms	23356 KiB

city

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

const int MAXN = 1e5 + 7;
const int logo = 17;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

struct uf{
	int par[MAXN], sz[MAXN];
	
	void res(){
		for(int i=0; i<MAXN; i++) par[i] = i, sz[i] = 0;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	bool unite(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
		return 1;
	}
}t;

unordered_map<ll, int> id, inp, ve;
ll ans;

ll vl(ll a, ll b){
	return a * MAXN + b;
}


vi g[MAXN];
int siz[MAXN], n;

void dfs(int u, int p = -1){
	for(auto &x : g[u]){
		if(x == p) continue;
		dfs(x, u);
		siz[u] += siz[x];
	}
	
	for(auto &x : g[u]){
		if(x == p) continue;
		//cout << u << " " << x << " " << n << " " << siz[x] << "\n";
		ans += (ll)siz[x] * (ll)(n - siz[x]);
	}
}

ll calc(int _n, int *x, int *y){
	//cout << "\n";
	n = _n;
	id.clear(), inp.clear(), ve.clear();
	for(int i=0; i<MAXN; i++) g[i].clear();
	t.res();
	ans = 0;
	
	vi a, b;
	for(int i=0; i<n; i++) a.PB(x[i]), b.PB(y[i]), t.sz[i] = 1;
	
	int mi = a[0], mj = b[0];
	for(auto &c : a) mi = min(mi, c);
	for(auto &c : b) mj = min(mj, c);
	for(auto &c : a) c -= mi;
	for(auto &c : b) c -= mj;
	
	for(int i=0; i<n; i++){
		id[vl(a[i], b[i])] = i;
		inp[vl(a[i], b[i])] = 1;
	}
	
	for(int i=0; i<n; i++){
		int cx = a[i] - 1, cy = b[i];
		ll j = vl(cx, cy);
		if(inp[j]){
			j = id[j];
			t.unite(i, j);
		}
	}
	
	for(int i=0; i<MAXN; i++) siz[i] = t.sz[i];
	
	for(int i=0; i<n; i++){
		int cx = a[i], cy = b[i] - 1;
		ll j = vl(cx, cy);
		if(!inp[j]) continue;
		j = id[j];
		
		int ni = t.find(i);
		int nj = t.find(j);
		ll cos = vl(ni, nj);
		ll cos2 = vl(nj, ni);
		if(ve[cos] == 0){
			ve[cos] = 1;
			ve[cos2] = 1;
			g[ni].PB(nj);
			g[nj].PB(ni);
		}
	}
	
	for(int i=0; i<MAXN; i++) if(t.find(i) == i and t.sz[i]){
		dfs(i);
		break;
	}
	return ans;
}

int DistanceSum(int _n, int *x, int *y){
	return ((ll)calc(_n, x, y) + (ll)calc(_n, y, x)) % mod;
}

/*
int xx[MAXN], yy[MAXN];
void solve(){
	int _n;
	cin >> _n;
	for(int i=0; i<_n; i++) cin >> xx[i] >> yy[i];
	cout << DistanceSum(_n, xx, yy) << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int _ = 1;
	//cin >> _;
	while(_--) solve();
	return 0;
}


*/

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