Submission #462609

#TimeUsernameProblemLanguageResultExecution timeMemory
462609JovanBCountries (BOI06_countries)C++17
100 / 100
5 ms384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; int par[100005]; int x[100005]; int y[100005]; int s[100005]; struct broj{ int p, q; bool operator <(const broj & a) const{ return p * a.q < a.p * q; } bool operator ==(const broj & a) const{ return p * a.q == a.p * q; } }; int dist(int j, int i){ return (x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]); } broj infl(int j, int i){ return {s[j], dist(j, i)}; } int root(int a){ if(par[a] == a) return a; return root(par[a]); } int main(){ ios_base::sync_with_stdio(false); cout.precision(10); cout<<fixed; int n; cin >> n; for(int i=1; i<=n; i++){ cin >> x[i] >> y[i] >> s[i]; } for(int i=1; i<=n; i++){ broj mx; mx.q = 0; for(int j=1; j<=n; j++){ if(i == j) continue; if(mx.q == 0) mx = infl(j, i); else if(mx < infl(j, i)) mx = infl(j, i); } if(mx.p <= s[i]*mx.q){ par[i] = i; continue; } for(int j=1; j<=n; j++){ if(j == i) continue; if(mx == infl(j, i)){ if(!par[i]) par[i] = j; else par[i] = -1; } } } for(int i=1; i<=n; i++){ if(par[i] == i) cout << "K\n"; else if(par[i] == -1) cout << "D\n"; else cout << root(i) << "\n"; } return 0; }

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:18:18: warning: 'mx.broj::p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |         return p * a.q == a.p * q;
      |                ~~^~~~~
countries.cpp:46:14: note: 'mx.broj::p' was declared here
   46 |         broj mx;
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...