Submission #430617

#	Time	Username	Problem	Language	Result	Execution time	Memory
430617		ak2006	Countries (BOI06_countries)	C++14	100 / 100	12 ms	460 KiB

countries

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
}
int compare(vi&f,vi&s,vi&p)
{
    return f[2] * ((s[0] - p[0]) * (s[0] - p[0]) + (s[1] - p[1]) * (s[1] - p[1]))
    -
    s[2] * ((f[0] - p[0]) * (f[0] - p[0]) + (f[1] - p[1]) * (f[1] - p[1]));
}
struct DSU
{
    int n;
    vi p,type;
    DSU(int N)
    {
        n = N;
        p.assign(n + 1,0);
        type.assign(n + 1,0);//0 means a kingdom
        for (int i = 1;i<=n;i++)p[i] = i;
    }
    int Find(int u)
    {
        if (p[u] == u)return u;
        return p[u] = Find(p[u]);
    }
    void Unite(int a,int b)//merge b into a
    {
        a = Find(a),b = Find(b);
        p[b] = a;
    }
};
int main()
{
    setIO();
    int n;
    cin>>n;
    vvi a(n,vi(3));
    DSU val(n);
    for (int i = 0;i<n;i++)cin>>a[i][0]>>a[i][1]>>a[i][2];
    for (int i = 0;i<n;i++){
        int bestPos = (i == 0 ? 1 : 0);
        int cntBest = 1;
        for (int j = 0;j<n;j++){
            if (i == j or j == bestPos)continue;
            int val = compare(a[j],a[bestPos],a[i]);
            if (val == 0)
                cntBest++;
            if (val > 0)
                bestPos = j,cntBest = 1;
        }
        if ((a[i][2] * ((a[i][0] - a[bestPos][0]) * (a[i][0] - a[bestPos][0]) +
            (a[i][1] - a[bestPos][1]) * (a[i][1] - a[bestPos][1]))) < a[bestPos][2]){
            if (cntBest >= 2){
                val.type[i] = 1;//1 means a democracy
            }
            else{
                val.Unite(bestPos,i);
            }
        }
    }
    for (int i = 0;i<n;i++){
        int cap = val.Find(i);
        if (cap != i)cout<<cap + 1<<'\n';
        else if (val.type[i] == 0)cout<<"K"<<'\n';
        else cout<<"D"<<'\n';
    }
    return 0;
}

• Subtask 1: 100 / 100