제출 #105549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105549		wilwxk	이상적인 도시 (IOI12_city)	C++11	100 / 100	764 ms	24184 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point {
	int x, y;
	bool operator<(point viz) const {
		if(x==viz.x) return y<viz.y;
		return x<viz.x;
	}
};

const int MAXN=1e5+5;
const int MOD=1e9;
const ll MODL=1e10;
point p[MAXN];
vector<int> g[2][MAXN];
map< pair<int, int>, int > mp;
int rep[2][MAXN];
int peso[2][MAXN];
ll dp[2][MAXN], soma[2][MAXN];
short marc[2][MAXN];
ll respf;

bool cmp(point a, point b) {
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

void predfs(int cur, int p, int k) {
	marc[k][cur]=1;
	dp[k][cur]=0; soma[k][cur]=peso[k][cur];
	// printf("predfs %d %d %d\n", cur, p, k);
	for(auto viz : g[k][cur]) {
		if(marc[k][viz]) continue;
		predfs(viz, cur, k);
		// printf("  %d pegou %d (%d)\n", cur, viz, (dp[k][viz]+soma[k][viz]));
		soma[k][cur]+=soma[k][viz];
		dp[k][cur]+=(dp[k][viz]+soma[k][viz]);
	}
}

void dfs(int cur, int p, int k) {
	marc[k][cur]=2;
	// printf("dp[%d][%d] = %d\n", k, cur, dp[k][cur]);
	respf+=((dp[k][cur]%MODL)*(peso[k][cur]%MODL))%MODL;
	respf%=MODL;
	for(auto viz : g[k][cur]) {
		if(marc[k][viz]==2) continue;

		ll dpkc=dp[k][cur];
		ll dpkv=dp[k][viz];
		ll somakc=soma[k][cur];
		ll somakv=soma[k][viz];

		dp[k][cur]-=dp[k][viz];
		dp[k][cur]-=soma[k][viz];
		soma[k][cur]-=soma[k][viz];
		soma[k][viz]+=soma[k][cur];
		dp[k][viz]+=dp[k][cur];
		dp[k][viz]+=soma[k][cur];

		dfs(viz, cur, k);

		dp[k][cur]=dpkc;
		dp[k][viz]=dpkv;
		soma[k][cur]=somakc;
		soma[k][viz]=somakv;
	}
}

int find(int z, int k) {
	if(rep[k][z]==z) return z;
	return rep[k][z]=find(rep[k][z], k);
}
void une(int a, int b, int k) {
	a=find(a, k); b=find(b, k);
	if(a==b) return;
	if(rand()&1) swap(a, b);
	rep[k][a]=b;
	peso[k][b]+=peso[k][a];
}

void liga(int a, int b, int k) {
	if(a==b) return;
	a=find(a, k);
	b=find(b, k);
	g[k][a].push_back(b);
	g[k][b].push_back(a);
	// printf("[%d] %d liga %d\n", k, a, b);
}

int DistanceSum(int n, int *x, int *y) {
	for(int i=0; i<n; i++) p[i].x=x[i], p[i].y=y[i];

	int aux=0; for(int i=0; i<n; i++) mp[{p[i].x, p[i].y}]=++aux;
	for(int i=0; i<=n; i++) rep[0][i]=i, rep[1][i]=i, peso[0][i]=1, peso[1][i]=1;

	//0- une os com o mesmo y
	sort(p, p+n);
	for(int i=0; i<n; i++) {
		int j=i;
		while(j+1<n&&p[j+1].x==p[i].x) {
			if(p[j].y+1==p[j+1].y) {
				int a=mp[{ p[j].x, p[j].y }];
				int b=mp[{ p[j+1].x, p[j+1].y }];
				une(a, b, 0);
			}
			j++;
		}
		i=j;
	}

	//1- une os com o mesmo x
	sort(p, p+n, cmp);
	for(int i=0; i<n; i++) {
		int j=i;
		while(j+1<n&&p[j+1].y==p[i].y) {
			if(p[j].x+1==p[j+1].x) {
				int a=mp[{ p[j].x, p[j].y }];
				int b=mp[{ p[j+1].x, p[j+1].y }];
				une(a, b, 1);
				// printf("une[1] %d e %d // ij %d %d // %d %d %d\n", a, b, i, j, p[j].x, p[j+1].x, p[j].y);
			}
			j++;
		}
		i=j;
	}

	// for(int i=0; i<n; i++) printf("comp %d > %d e %d > peso %d %d\n", i, find(mp[{x[i], y[i]}], 0), find(mp[{x[i], y[i]}], 1), peso[0][find(mp[{x[i], y[i]}], 0)], peso[1][find(mp[{x[i], y[i]}], 1)]);

	for(int i=0; i<n; i++) {
		if(mp.find({x[i]+1, y[i]})!=mp.end()) {
			int a=mp[{x[i], y[i]}]; int b=mp[{x[i]+1, y[i]}];
			liga(a, b, 0);
		}
		if(mp.find({x[i]-1, y[i]})!=mp.end()) {
			int a=mp[{x[i], y[i]}]; int b=mp[{x[i]-1, y[i]}];
			liga(a, b, 0);
		}
		if(mp.find({x[i], y[i]+1})!=mp.end()) {
			int a=mp[{x[i], y[i]}]; int b=mp[{x[i], y[i]+1}];
			liga(a, b, 1);
		}
		if(mp.find({x[i], y[i]-1})!=mp.end()) {
			int a=mp[{x[i], y[i]}]; int b=mp[{x[i], y[i]-1}];
			liga(a, b, 1);
		}
	}

	predfs(find(1, 0), find(1, 0), 0);
	predfs(find(1, 1), find(1, 1), 1); 
	// for(int i=1; i<=n; i++) printf("dp %d > %d %d\n", i, dp[0][i], dp[1][i]);

	respf=0;
	dfs(find(1, 0), find(1, 0), 0);
	dfs(find(1, 1), find(1, 1), 1);
	respf/=2;
	respf%=MOD;

	return respf;
}

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