Submission #926577

#	Time	Username	Problem	Language	Result	Execution time	Memory
926577		parlimoos	Countries (BOI06_countries)	C++14	100 / 100	3 ms	348 KiB

countries

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

struct ksr{
    int a , b;
    bool operator >(ksr &d){
        ll d1 = (1ll * a * 1ll * d.b) , d2 = (1ll * b * 1ll * d.a);
        return (d1 > d2);
    }
    bool operator <(ksr &d){
        ll d1 = (1ll * a * 1ll * d.b) , d2 = (1ll * b * 1ll * d.a);
        return (d1 < d2);
    }
    bool operator ==(ksr &d){
        ll d1 = (1ll * a * 1ll * d.b) , d2 = (1ll * b * 1ll * d.a);
        return (d1 == d2);
    }
};

const int INF = int(1e9);

int n;
vector<arr(2)> a;
int s[1000];
int dsu[1000] , o[1000];

int findDsu(int v){
    if(dsu[v] == -1) return v;
    return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
    a = findDsu(a) , b = findDsu(b);
    if(a != b) dsu[b] = a;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    fill(&dsu[0] , &dsu[n] , -1);
    for(int i = 0 ; i < n ; i++){
        int x , y , d;
        cin >> x >> y >> d;
        a.pb({x , y});
        s[i] = d;
    }
    for(int i = 0 ; i < n ; i++){
        ksr mx;
        mx.a = -INF , mx.b = 1;
        int inx = n + 1;
        for(int j = 0 ; j < n ; j++){
            if(j == i) continue;
            int x = abs(a[i][0] - a[j][0]) , y = abs(a[i][1] - a[j][1]);
            ksr d;
            d.a = s[j] , d.b = ((x * x) + (y * y));
            if(mx < d) mx = d , inx = j;
            else if(mx == d) inx = n + 1;
        }
        ksr d;
        d.a = s[i] , d.b = 1;
        if(!(mx > d)) o[i] = -2;
        else if(inx == n + 1) o[i] = -1;
        else o[i] = 0 , uDsu(inx , i);
    }
    for(int i = 0 ; i < n ; i++){
        if(o[i] == -2) cout << "K\n";
        else if(o[i] == -1) cout << "D\n";
        else cout << findDsu(i) + 1 << endl;
    }
}

• Subtask 1: 100 / 100