oj.uz

Submission #274595

# Submission time Handle Problem Language Result Execution time Memory
274595 2020-08-19T13:00:44 Z amoo_safar Ideal city (IOI12_city) C++17
100 / 100
 203 ms 11632 KB 
// That's How much we have in common
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

typedef pair<int, int> pii;

const int Mod = 1'000'000'000;
const int N = 2e5 + 10;

int mul(int a, int b){
	return (1ll * a * b) % Mod;
}
int ans, n;
void Add(int x){
	ans += x;
	ans %= Mod;
}
vector<pii> P;
int Id(pii A){
	auto it = lower_bound(P.begin(), P.end(), A);
	if(it == P.end() || *it != A) return -1;
	return it - P.begin();
}
pii del[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int flg[4] = {0, 0, 1, 1};
int mk[N];

int DFS(int u){
	int sub = 1;
	int adj, res;
	int x = P[u].F, y = P[u].S;
	while(Id({x, y}) != -1 && !mk[Id({x, y})]){
		x += del[0].F;
		y += del[0].S;
	}
	x -= del[0].F;
	y -= del[0].S;
	u = Id({x, y});
	mk[u] = 1;
	for(int i = 1; i < 4; i++){
		x = P[u].F + del[i].F;
		y = P[u].S + del[i].S;
		adj = Id({x, y});
		if(adj == -1 || mk[adj]) continue;
		res = DFS(adj);
		sub += res;
		if(flg[i])
			Add(mul(res, n - res));
	}
	return sub;
}

int DistanceSum(int _n, int *X, int *Y) {
	n = _n;
	ans = 0;
	P.clear();
	for(int i = 0; i < n; i++) P.pb({X[i], Y[i]});
	sort(P.begin(), P.end());

	memset(mk, 0, sizeof mk);
	DFS(0);
	swap(del[0], del[2]);
	swap(del[1], del[3]);
	memset(mk, 0, sizeof mk);
	DFS(0);
	return ans;
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6

7
1 2
2 1
2 2
2 3
3 1
3 2
3 3

*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3188 KB Output is correct
2 Correct 32 ms 3316 KB Output is correct
3 Correct 89 ms 6392 KB Output is correct
4 Correct 85 ms 6388 KB Output is correct
5 Correct 186 ms 11376 KB Output is correct
6 Correct 179 ms 11376 KB Output is correct
7 Correct 203 ms 11480 KB Output is correct
8 Correct 200 ms 11632 KB Output is correct
9 Correct 176 ms 11376 KB Output is correct
10 Correct 147 ms 11504 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1788 KB Output is correct
2 Correct 31 ms 2428 KB Output is correct
3 Correct 78 ms 2676 KB Output is correct
4 Correct 76 ms 3452 KB Output is correct
5 Correct 151 ms 4080 KB Output is correct
6 Correct 168 ms 5360 KB Output is correct
7 Correct 167 ms 4336 KB Output is correct
8 Correct 157 ms 5104 KB Output is correct
9 Correct 164 ms 4080 KB Output is correct
10 Correct 164 ms 4568 KB Output is correct