oj.uz

Submission #880895

# Submission time Handle Problem Language Result Execution time Memory
880895 2023-11-30T08:13:34 Z noompty Countries (BOI06_countries) C++17
100 / 100
 69 ms 16720 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

int n, ans[1005], in[1005];
array<int, 3> cities[1005];
vector<pair<double, int>> infl[1005];
vector<int> adj[1005];

void dfs(int curr, int v) {
    if (ans[curr] != 0) ans[curr] = v;
    for (int i : adj[curr]) {
        dfs(i, v);
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    if (n == 1) {
        cout << "K\n";
        exit(0);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> cities[i][j];
        }
        infl[i].push_back({0, -1});
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            infl[i].push_back({(double) cities[j][2] / (double) ((cities[j][1] - cities[i][1]) * (cities[j][1] - cities[i][1]) + (cities[j][0] - cities[i][0]) * (cities[j][0] - cities[i][0])), j});
        }
        sort(infl[i].begin(), infl[i].end());
    }

    fill(ans, ans + 1005, -1);
    for (int i = 0; i < n; i++) {
        if (infl[i].back().f <= cities[i][2]) {
            ans[i] = 0;
        } else {
            if (infl[i].size() > 2 && infl[i].back().f == infl[i][infl[i].size() - 2].f) {
                ans[i] = -2;
            } else {
                assert(infl[i].back().s != -1);
                adj[infl[i].back().s].push_back(i);
                in[i]++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (adj[i].size() && !in[i]) dfs(i, i + 1);
    }

    for (int i = 0; i < n; i++) {
        if (ans[i] == 0) cout << "K\n";
        else if (ans[i] == -2) cout << "D\n";
        else cout << ans[i] << "\n";
    }

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 7 ms 2796 KB Output is correct
4 Correct 11 ms 3676 KB Output is correct
5 Correct 16 ms 4444 KB Output is correct
6 Correct 25 ms 8200 KB Output is correct
7 Correct 34 ms 10836 KB Output is correct
8 Correct 44 ms 13176 KB Output is correct
9 Correct 55 ms 14952 KB Output is correct
10 Correct 69 ms 16460 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 7 ms 2908 KB Output is correct
14 Correct 11 ms 3676 KB Output is correct
15 Correct 17 ms 4316 KB Output is correct
16 Correct 26 ms 8280 KB Output is correct
17 Correct 33 ms 10832 KB Output is correct
18 Correct 43 ms 13136 KB Output is correct
19 Correct 45 ms 14748 KB Output is correct
20 Correct 69 ms 16720 KB Output is correct