oj.uz

Submission #82539

# Submission time Handle Problem Language Result Execution time Memory
82539 2018-10-31T11:20:57 Z leejseo Ideal city (IOI12_city) C++11
100 / 100
 80 ms 21720 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lld;
typedef pair<int, int> point;

#define x first
#define y second

const lld MOD = 1000000000;

int A[100000];
point T[100000];
int B[100000];
vector<point> L[100000];
lld ans = 0;
vector<int> adj[100000];
bool chk[100000];
bool vis[100000];

int M;

void init(){
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	for (int i=0; i<100000; i++){
		L[i].clear();
		T[i] = point(0, 0);
		adj[i].clear();
	}
	memset(chk, 0, sizeof(chk));
	memset(vis, 0, sizeof(vis));
}

int dfs(int i){
	vis[i] = 1;
	int ret = 0;
	for (int j: adj[i])
		if (!vis[j])
			ret += dfs(j);
	ret += L[i].size();
	ans = (ans + 1LL*ret*(M-ret))%MOD;
	return ret;
}

void compute_dist(int N, int *X, int *Y){
	M = N;
	for (int i=0; i<N; i++){
		T[i] = point(X[i], Y[i]);
	}
	sort(T, T+N);
	L[0].push_back(T[0]);
	int tot = 0;    
	for (int i=1; i<N; i++){
		if (L[tot].back().x == T[i].x && L[tot].back().y + 1 == T[i].y)
			L[tot].push_back(T[i]);
		else
			L[++tot].push_back(T[i]);	
		B[i] = tot;
	}
	++tot;
	int s = 1, e = 1;
	for (int i=0; i<tot; i++){
		while (true){
			if (s == tot) break;
			if (L[s][0].x <= L[i][0].x) s++;
			else{ 
				if (L[i][0].x + 1 == L[s][0].x && L[s].back().y < L[i][0].y) s++;
				else break;
			}
		}
		while (true){
			if (e == tot) break;
			if (L[e][0].x <= L[i][0].x) e++;
			else{
				if (L[i][0].x + 1 == L[e][0].x && L[e][0].y <= L[i].back().y) e++;
				else break;
			}
		}
		for (int j=s; j<e; j++){
			adj[i].push_back(j);
			adj[j].push_back(i);
		}
	}
	dfs(0);
}

int DistanceSum(int N, int *X, int *Y) {
	compute_dist(N, X, Y);
	init();
	compute_dist(N, Y, X);
  return ans;

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6748 KB Output is correct
2 Correct 8 ms 6784 KB Output is correct
3 Correct 7 ms 6864 KB Output is correct
4 Correct 10 ms 6912 KB Output is correct
5 Correct 9 ms 7020 KB Output is correct
6 Correct 8 ms 7020 KB Output is correct
7 Correct 8 ms 7032 KB Output is correct
8 Correct 8 ms 7036 KB Output is correct
9 Correct 7 ms 7060 KB Output is correct
10 Correct 8 ms 7192 KB Output is correct
11 Correct 8 ms 7192 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7192 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 10 ms 7340 KB Output is correct
4 Correct 8 ms 7340 KB Output is correct
5 Correct 9 ms 7384 KB Output is correct
6 Correct 8 ms 7392 KB Output is correct
7 Correct 12 ms 7424 KB Output is correct
8 Correct 11 ms 7456 KB Output is correct
9 Correct 11 ms 7468 KB Output is correct
10 Correct 10 ms 7476 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8004 KB Output is correct
2 Correct 20 ms 8408 KB Output is correct
3 Correct 35 ms 9056 KB Output is correct
4 Correct 32 ms 9948 KB Output is correct
5 Correct 55 ms 11312 KB Output is correct
6 Correct 69 ms 13112 KB Output is correct
7 Correct 57 ms 13688 KB Output is correct
8 Correct 55 ms 13688 KB Output is correct
9 Correct 73 ms 15284 KB Output is correct
10 Correct 63 ms 18560 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18560 KB Output is correct
2 Correct 20 ms 18560 KB Output is correct
3 Correct 41 ms 18560 KB Output is correct
4 Correct 39 ms 18560 KB Output is correct
5 Correct 74 ms 19224 KB Output is correct
6 Correct 62 ms 19224 KB Output is correct
7 Correct 80 ms 20816 KB Output is correct
8 Correct 61 ms 20816 KB Output is correct
9 Correct 69 ms 20972 KB Output is correct
10 Correct 64 ms 21720 KB Output is correct