oj.uz

Submission #105549

# Submission time Handle Problem Language Result Execution time Memory
105549 2019-04-13T11:44:24 Z wilwxk Ideal city (IOI12_city) C++11
100 / 100
 764 ms 24184 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 10 ms 5376 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 10 ms 5376 KB Output is correct
6 Correct 11 ms 5504 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 11 ms 5400 KB Output is correct
9 Correct 14 ms 5504 KB Output is correct
10 Correct 13 ms 5376 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8668 KB Output is correct
2 Correct 89 ms 8696 KB Output is correct
3 Correct 299 ms 14280 KB Output is correct
4 Correct 240 ms 13560 KB Output is correct
5 Correct 626 ms 24184 KB Output is correct
6 Correct 631 ms 22548 KB Output is correct
7 Correct 647 ms 23648 KB Output is correct
8 Correct 662 ms 23544 KB Output is correct
9 Correct 637 ms 21452 KB Output is correct
10 Correct 604 ms 23660 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8552 KB Output is correct
2 Correct 88 ms 8960 KB Output is correct
3 Correct 286 ms 14144 KB Output is correct
4 Correct 276 ms 14456 KB Output is correct
5 Correct 719 ms 22884 KB Output is correct
6 Correct 697 ms 23884 KB Output is correct
7 Correct 686 ms 23064 KB Output is correct
8 Correct 750 ms 23772 KB Output is correct
9 Correct 713 ms 23540 KB Output is correct
10 Correct 764 ms 23800 KB Output is correct