oj.uz

Submission #926577

# Submission time Handle Problem Language Result Execution time Memory
926577 2024-02-13T10:52:10 Z parlimoos Countries (BOI06_countries) C++14
100 / 100
 3 ms 348 KB 
//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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 348 KB Output is correct