Submission #274595

#	Time	Username	Problem	Language	Result	Execution time	Memory
274595		amoo_safar	Ideal city (IOI12_city)	C++17	100 / 100	203 ms	11632 KiB

city

// 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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45