oj.uz

Submission #105544

# Submission time Handle Problem Language Result Execution time Memory
105544 2019-04-13T11:19:45 Z wilwxk Ideal city (IOI12_city) C++11
32 / 100
 101 ms 8700 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;
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]);
	ll val=(dp[k][cur]*peso[k][cur]); respf+=val;
	if(respf>MOD) respf%=MOD;
	for(auto viz : g[k][cur]) {
		if(marc[k][viz]==2) continue;

		int dpkc=dp[k][cur];
		int dpkv=dp[k][viz];
		int somakc=soma[k][cur];
		int 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%=MOD;

	return respf/2;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 9 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 9 ms 5248 KB Output is correct
3 Correct 11 ms 5376 KB Output is correct
4 Correct 10 ms 5376 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 14 ms 5504 KB Output is correct
7 Correct 12 ms 5504 KB Output is correct
8 Correct 13 ms 5504 KB Output is correct
9 Correct 15 ms 5376 KB Output is correct
10 Correct 12 ms 5376 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 8700 KB Output is correct
2 Incorrect 101 ms 8668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 8492 KB Output isn't correct
2 Halted 0 ms 0 KB -