Submission #932181

#	Time	Username	Problem	Language	Result	Execution time	Memory
932181		teacup	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3104 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define vi vector<int>
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<ii> vii;

struct Comp{
	bool operator()(const iiii a, const iiii b){
		if (get<2>(a)!=get<2>(b)) return get<2>(a) < get<2>(b); else return get<3>(a) > get<3>(b);
	}
};

int32_t main(){
	int n,x,y,r,idx; cin>>n;
	vector<iiii> V;
	vi AL[n];
	for (int i=0; i<n; i++){
		cin>>x>>y>>r;
		V.emplace_back(iiii({x,y,r,i}));
	}
	for (int i=0; i<n; i++){
		for (int j=i+1; j<n; j++){
			if ((get<0>(V[i])-get<0>(V[j]))*(get<0>(V[i])-get<0>(V[j]))
			+ (get<1>(V[i])-get<1>(V[j]))*(get<1>(V[i])-get<1>(V[j]))
			<= (get<2>(V[i])+get<2>(V[j]))*(get<2>(V[i])+get<2>(V[j]))){
				AL[i].emplace_back(j);
				AL[j].emplace_back(i);
			}
		}
	}
	priority_queue<iiii, vector<iiii>, Comp> PQ;
	
	for (int i=0; i<n; i++){
		PQ.push(V[i]);
	}
	
	bool vis[n]={};
	int ans[n];
	while (!PQ.empty()){
		iiii curr=PQ.top(); PQ.pop();
		idx = get<3>(curr);
		if (vis[idx]) continue;
		ans[idx]=idx;
		for (auto nb : AL[idx]){
			if (!vis[nb]){
				vis[nb]=true;
				ans[nb]=idx;
			}
		}
	}
	
	for (int i=0; i<n; i++) cout<<ans[i]+1<<" ";
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13