Submission #925524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925524	2024-02-11T22:46:58 Z	Karoot	Countries (BOI06_countries)	C++17	100 / 100	214 ms	78676 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1116 KB	Output is correct
2	Correct	7 ms	3420 KB	Output is correct
3	Correct	17 ms	7388 KB	Output is correct
4	Correct	29 ms	12892 KB	Output is correct
5	Correct	46 ms	19812 KB	Output is correct
6	Correct	69 ms	28496 KB	Output is correct
7	Correct	97 ms	38740 KB	Output is correct
8	Correct	129 ms	50516 KB	Output is correct
9	Correct	168 ms	63728 KB	Output is correct
10	Correct	209 ms	78676 KB	Output is correct
11	Correct	2 ms	1116 KB	Output is correct
12	Correct	8 ms	3676 KB	Output is correct
13	Correct	15 ms	7516 KB	Output is correct
14	Correct	32 ms	12880 KB	Output is correct
15	Correct	47 ms	19792 KB	Output is correct
16	Correct	69 ms	28496 KB	Output is correct
17	Correct	96 ms	38776 KB	Output is correct
18	Correct	127 ms	50516 KB	Output is correct
19	Correct	176 ms	63852 KB	Output is correct
20	Correct	214 ms	78564 KB	Output is correct