oj.uz

Submission #99914

# Submission time Handle Problem Language Result Execution time Memory
99914 2019-03-08T17:01:43 Z jhnah917 Ideal city (IOI12_city) C++14
68 / 100
 292 ms 24956 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int mod = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int uf[101010];
int size[101010];
int chk[101010];
int n;
set<int> g[101010];

int find(int v){
	return uf[v] == v ? v : uf[v] = find(uf[v]);
}

void merge(int u, int v){
	u = find(u), v = find(v);
	if(u^v) uf[u] = v;
}

void dfs(int now, int prv, int &dist){ //거리 구하기 
	for(auto nxt : g[now]){
		if(nxt^prv && !chk[nxt]){
			chk[nxt] = 1;
			dfs(nxt, now, dist);
			size[now] += size[nxt];
		}
	}
	ll tmp = (ll)size[now] * (ll)(n - size[now]);
	tmp %= mod;
	dist += tmp; dist %= mod;
}

int getDist(){
	int ret = 0;
	chk[find(0)+1] = 1;
	for(int i=0; i<n; i++) size[find(i)+1]++;
	dfs(find(0)+1, 0, ret);
	return ret;
}

void makeTree(vector<p> &v){
	//init
	map<p, int> mp;
	sort(v.begin(), v.end());
	memset(size, 0, sizeof size);
	memset(chk, 0, sizeof chk);
	for(int i=0; i<n; i++) g[i].clear();
	for(int i=0; i<=n+1; i++) uf[i] = i;
	
	//union
	for(int i=0; i<n-1; i++){
		if(v[i].x == v[i+1].x && v[i].y+1 == v[i+1].y){
			merge(i, i+1);
		}
	}
	for(int i=0; i<n; i++){
		mp[{v[i].x, v[i].y}] = find(i)+1;
	}
	
	//make
	for(int i=0; i<n; i++){
		int x = v[i].x, y = v[i].y;
		for(int k=0; k<4; k++){
			int xx = x + dx[k], yy = y + dy[k];
			int nxt = mp[{xx, yy}];
			if(nxt != 0 && find(i)+1 != nxt) g[find(i)+1].insert(nxt);
		}
	}
}

int DistanceSum(int N, int *X, int *Y){
	n = N;
	int ret = 0;
	vector<p> v(n);
	for(int i=0; i<n; i++){
		v[i] = {X[i], Y[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	
	for(int i=0; i<n; i++){
		v[i] = {Y[i], X[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	ret %= mod;
	return ret;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 7 ms 5888 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 9 ms 5888 KB Output is correct
5 Correct 9 ms 5888 KB Output is correct
6 Incorrect 9 ms 5888 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7880 KB Output is correct
2 Correct 44 ms 8024 KB Output is correct
3 Correct 96 ms 10744 KB Output is correct
4 Correct 101 ms 10744 KB Output is correct
5 Correct 211 ms 15180 KB Output is correct
6 Correct 213 ms 15352 KB Output is correct
7 Correct 191 ms 15780 KB Output is correct
8 Correct 202 ms 15160 KB Output is correct
9 Correct 206 ms 16016 KB Output is correct
10 Correct 261 ms 24312 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9600 KB Output is correct
2 Correct 48 ms 8952 KB Output is correct
3 Correct 145 ms 15312 KB Output is correct
4 Correct 116 ms 13532 KB Output is correct
5 Correct 292 ms 24404 KB Output is correct
6 Correct 217 ms 18808 KB Output is correct
7 Correct 260 ms 24956 KB Output is correct
8 Correct 232 ms 19068 KB Output is correct
9 Correct 240 ms 17792 KB Output is correct
10 Correct 230 ms 17528 KB Output is correct