oj.uz

Submission #274541

# Submission time Handle Problem Language Result Execution time Memory
274541 2020-08-19T12:43:25 Z amoo_safar Ideal city (IOI12_city) C++17
0 / 100
 24 ms 2556 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;
	mk[u] = 1;
	int x, y, adj, res;
	for(int i = 0; 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

*/

Subtask #1
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 Incorrect 1 ms 1152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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