Submission #511139

#TimeUsernameProblemLanguageResultExecution timeMemory
511139inventiontimeCountries (BOI06_countries)C++17
20 / 100
5 ms332 KiB
#include<bits/stdc++.h> using namespace std; #define int ll //#define endl '\n' #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define pb push_back #define re(x, n) x.clear(); x.resize(n) #define all(x) (x).begin(), (x).end() #define loop(i, n) for(int i = 0; i < n; i++) #define loop1(i, n) for(int i = 1; i <= n; i++) #define print(x) cout << #x << ": " << x << endl //#define maxn ((int) 1e5 + 5) #define inf ((int) 1e17) typedef long long ll; typedef priority_queue<int> pq; typedef vector<int> vi; typedef array<int, 2> ii; typedef array<int, 3> ti; typedef vector<ii> vii; typedef vector<ti> vti; template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a,b); return B; } template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a,b); return B; } int n; vti city; vti top_threat; int dist(int i, int j) { return abs(city[i][0] - city[j][0])*abs(city[i][0] - city[j][0]) + abs(city[i][1] - city[j][1])*abs(city[i][1] - city[j][1]); } bool threat(int i, int j) { // check if i is threatened by j return city[i][2] * dist(i, j) < city[j][2]; } ti calc_threat(ti t1, ti t2) { if(t1[0] * t2[1] == t1[1] * t2[0]) { return {t1[0], t1[1], -2}; } else if(t1[0] * t2[1] > t1[1] * t2[0]) { // influence of t1 is greater return t1; } else { return t2; } } void solve() { cin >> n; re(city, n); re(top_threat, n); loop(i, n) { int x, y, s; cin >> x >> y >> s; city[i] = {x, y, s}; top_threat[i] = {-1, 1, -1}; } loop(i, n) loop(j, n) if(i != j) { if(threat(i, j)) top_threat[i] = calc_threat(top_threat[i], {city[j][3], dist(i, j), j}); } loop(i, n) { int j = i; while(top_threat[j][2] >= 0) j = top_threat[j][2]; if(j == i) cout << (top_threat[j][2] == -1 ? "K" : "D") << endl; else cout << j+1 << endl; } } signed main(){ fast_io; int t = 1; //cin >> t; while(t--) solve(); //cout << flush; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...