제출 #519107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519107		AdamGS	Ideal city (IOI12_city)	C++17	100 / 100	70 ms	9540 KiB

city

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll MOD=1e9;
vector<int>V[LIM];
pair<int,int>T[LIM];
map<int,int>mp;
ll F[LIM], ile[LIM], n, ans;
int fnd(int x) {
	if(F[x]==x) return x;
	return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
	if(fnd(a)==fnd(b)) return;
	ile[fnd(a)]+=ile[fnd(b)];
	F[fnd(b)]=fnd(a);
}
ll DFS(int x, int o) {
	ll s=ile[x];
	for(auto i : V[x]) if(i!=o) s+=DFS(i, x);
	ans+=s*(n-s);
	ans%=MOD;
	return s;
}
int DistanceSum(int N, int *X, int *Y) {
	n=N;
	rep(i, n) T[i]={X[i], Y[i]};
	rep(j, 2) {
		mp.clear();
		rep(i, n) {
			swap(T[i].st, T[i].nd);
			F[i]=i;
			ile[i]=1;
			V[i].clear();
		}
		sort(T, T+n);
		rep(i, n-1) {
			if(T[i].st==T[i+1].st && T[i].nd+1==T[i+1].nd) uni(i, i+1);
		}
		rep(i, n) {
			int x=mp[T[i].nd]-1;
			if(x>=0 && T[x].st==T[i].st-1 && (!V[fnd(i)].size() || V[fnd(i)].back()!=fnd(x))) {
				V[fnd(i)].pb(fnd(x));
				V[fnd(x)].pb(fnd(i));
			}
			mp[T[i].nd]=i+1;
		}
		DFS(fnd(0), fnd(0));
	}
	return ans;
}

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