Submission #33841

#	Time	Username	Problem	Language	Result	Execution time	Memory
33841		cprayer	개구리 (KOI13_frog)	C++14	0 / 22	159 ms	4700 KiB

frog

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long long unsigned llu;
typedef long double ld;

const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 1e5 + 9;

struct point{
	int x, y;
};

point arr[MAX_N];
int f[MAX_N];
int N, r, d;

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

void merge(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v) return;
	if(u > v) swap(u, v);
	f[v] = u;
}

void visit(int type){
	if(type){
		for(int i = 0; i < N; i++) swap(arr[i].x, arr[i].y);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqmin;
	map<int, int> curr;
	set<pair<int, int>> cand;
	for(int i = 0; i < N; i++){
		while(!pqmin.empty() && pqmin.top().first + r + d < arr[i].x){
			int p = pqmin.top().second;
			if(curr[arr[p].y] == 1){
				cand.erase({arr[p].y, p});
				curr[arr[p].y]--;
			}
			pqmin.pop();
		}
		auto it = cand.lower_bound({arr[i].y - r, -inf});
		if(it != cand.end()){
			if(it->first <= arr[i].y + r) merge(it->second, i);
		}
		pqmin.push({arr[i].x, i});
		if(!curr[arr[i].y]) cand.insert({arr[i].y, i});
		curr[arr[i].y]++;
	}
	while(!pqmin.empty()) pqmin.pop();
	curr.clear();
	cand.clear();
	priority_queue<pair<int, int>> pqmax;
	for(int i = N - 1; i >= 0; i--){
		while(!pqmax.empty() && arr[i].x + r + d < pqmax.top().first){
			int p = pqmax.top().second;
			if(curr[arr[p].y] == 1){
				cand.erase({arr[p].y, p});
				curr[arr[p].y]--;
			}
			pqmax.pop();
		}
		auto it = cand.lower_bound({arr[i].y - r, -inf});
		if(it != cand.end()){
			if(it->first <= arr[i].y + r) merge(it->second, i);
		}
		pqmax.push({arr[i].x, i});
		if(!curr[arr[i].y]) cand.insert({arr[i].y, i});
		curr[arr[i].y]++;
	}
	while(!pqmax.empty()) pqmax.pop();
	curr.clear();
	cand.clear();
	if(type){
		for(int i = 0; i < N; i++) swap(arr[i].x, arr[i].y);
	}
}

int main(){
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	cin >> N >> r;
	for(int i = 0; i < N; i++){
		int x, y;
		cin >> x >> y;
		arr[i] = {x, y};
	}
	for(int i = 0; i < N; i++) f[i] = i;
	cin >> d;
	sort(arr, arr + N, [](point &a, point &b){
		if(a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});
	visit(0);
	sort(arr, arr + N, [](point &a, point &b){
		if(a.y != b.y) return a.y < b.y;
		return a.x < b.x;
	});
	visit(1);
	ll ans = 0;
	for(int i = 0; i < N; i++) printf("%d ", find(i));
	printf("\n");
	for(int i = 0; i < N; i++){
		if(find(i) == 0) ans = max(ans, 1LL * arr[i].x + arr[i].y + 2 * r);
	}
	printf("%lld", ans);
	return 0;
}

• Subtask 1: 0 / 1.98
• Subtask 2: 0 / 2.64
• Subtask 3: 0 / 3.52
• Subtask 4: 0 / 4.18
• Subtask 5: 0 / 4.62
• Subtask 6: 0 / 5.06