Submission #925524

#	Time	Username	Problem	Language	Result	Execution time	Memory
925524		Karoot	Countries (BOI06_countries)	C++17	100 / 100	214 ms	78676 KiB

countries

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 1001;
int parent[MAXN];
bool isDemo[MAXN];

int rootOf(int x){
    return (x == parent[x] ? x : rootOf(parent[x]));
}

void merge(int a, int b){
    //a -> b
    parent[a] = rootOf(b);
}

/*
5
2 5 14
2 3 2
3 2 7
1 1 2
2 1 3

*/

set<pair<long double, int> > s[MAXN];

long double soldiers[MAXN];
vector<pair<ll, ll> > v;

long double dist(int i, int j){
    long double di = pow(abs(v[i].first-v[j].first), 2) + pow(abs(v[i].second-v[j].second), 2);
    return soldiers[j]/di;
}

long double di(int i, int j){
    long double di = pow(abs(v[i].first-v[j].first), 2) + pow(abs(v[i].second-v[j].second), 2);
    return di;
}

int main(){
    scoobydoobydoo();
    int n; cin >> n;
    for (int i = 0; i < n; i++){
        parent[i] = i;
        v.push_back({});
    }

    for (int i = 0; i < n; i++){
        ll x, y, w; cin >> x >> y >> w;
        v[i] = {x, y};
        soldiers[i] = w;
    }

    int counter = 0;
    for (auto p : v){
        int cntr = -1;
        for (auto e : v){
            cntr++;
            if (p == e)continue;
            s[counter].insert({dist(counter, cntr), cntr});
        }
        counter++;
    }
    cout << fixed << setprecision(10);


    for (int i = 0; i < n; i++){
        auto it = s[i].rbegin();
        pair<long double, int> firs = *it;
        it--;
        pair<long double, int> secon = *it;

        long double w1 = soldiers[firs.second]/soldiers[secon.second];
        long double s1 = di(i, firs.second)/di(i, secon.second);

        if (w1 == s1 && firs.first > soldiers[i]){
            //cout << i << " " << firs.first << " " << secon.first << " ; " << firs.second << " " << secon.second << endl;
            //cout << soldiers[firs.second] << " " << v[firs.second].first << " " << v[firs.second].second << endl;
            //cout << soldiers[secon.second] << " " << v[secon.second].first << " " << v[secon.second].second << endl;
            isDemo[i] = true;
        } else if (firs.first > soldiers[i]){
            merge(i, firs.second);
        } 
    }

    for (int i = 0; i < n; i++){
        if (isDemo[i]){
            cout << "D" << endl;
        } else if (parent[i] != i){
            cout << rootOf(i)+1 << endl;
        } else {
            cout << "K" << endl;
        }
    }
    


    return 0;
}

• Subtask 1: 100 / 100