Submission #307237

#TimeUsernameProblemLanguageResultExecution timeMemory
307237RainbowbunnyCountries (BOI06_countries)C++17
100 / 100
4 ms384 KiB
#include <bits/stdc++.h> #define mp make_pair #define eb emplace_back #define fi first #define se second using namespace std; using cd = complex <double>; const long long INF = 1e15; const int N = 3e5 + 2; //const int mod = 1e9 + 7;//998244353;//1e9 + 7;//786433; const double Pi = acos(-1); void Fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n; long long x[1005], y[1005], s[1005]; int ans[1005]; long long Dist(int i, int j) { return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); } int Root(int i) { return (ans[i] < 0 || ans[i] == i) ? i : ans[i] = Root(ans[i]); } signed main() { Fastio(); cin >> n; for(int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> s[i]; } for(int i = 1; i <= n; i++) { int cur = i; pair <long long, long long> Max = mp(-1, 1); for(int j = 1; j <= n; j++) { if(j == i) { continue; } if(Max.fi * Dist(i, j) < Max.se * s[j] and s[j] > Dist(i, j) * s[i]) { Max.fi = s[j]; Max.se = Dist(i, j); cur = j; } else if(Max.fi * Dist(i, j) == Max.se * s[j]) { cur = -1; } } ans[i] = cur; } for(int i = 1; i <= n; i++) { if(ans[i] < 0) { cout << 'D' << '\n'; } else if(ans[i] == i) { cout << 'K' << '\n'; } else { cout << Root(i) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...