Submission #198862

#TimeUsernameProblemLanguageResultExecution timeMemory
198862imaxblueCountries (BOI06_countries)C++17
100 / 100
8 ms380 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define vi vector<int> #define vpii vector<pii> #define vp3i vector<p3i> #define vpll vector<pll> #define vp3l vector<p3l> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() ((rand() << 14)+rand()) #define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0) char _; #define pi 3.14159265358979323846 #define startrng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, p[1005], sz[1005], r[1005]; bool flag[1005]; ll x[1005], y[1005], s[1005]; p3l top[1005]; int get(int A){ while(p[A]!=A) A=p[A]; return A; } void mrg(int A, int B){ A = get(A); B = get(B); if (sz[A] < sz[B]){ r[B] = r[A]; mrg(B, A); return; } p[B] = p[A]; sz[A] += sz[B]; } ll dis(int A, int B){ return (x[A]-x[B])*(x[A]-x[B])+(y[A]-y[B])*(y[A]-y[B]); } int32_t main(){ //what if all cities are in the same kingdom scanf("%i", &n); fox(l, n){ scanf("%lli%lli%lli", x+l, y+l, s+l); } fox(l, n){ p[l]=l; r[l]=l; sz[l]=1; } /*fox(l, n){ fox(l2, n){ cout << dis(l, l2) << ' '; } cout << endl; }*/ fox(l, n){ top[l] = mp(mp(s[l], 1), l); fox(l2, n){ if (l==l2) continue; if (top[l].x.x*dis(l, l2)<s[l2]*top[l].x.y){ //cout << "*" << l << ' ' << l2 << endl; top[l] = mp(mp(s[l2], dis(l, l2)), l2); flag[l] = 0; } else if (top[l].x.x*dis(l, l2)==s[l2]*top[l].x.y){ flag[l] = 1; } } } fox(l, n){ if (top[l].y!=l && !flag[l]) mrg(top[l].y, l); } fox(l, n){ if (top[l].y==l) printf("K\n"); else if (flag[l]) printf("D\n"); else printf("%i\n", r[get(l)]+1); } return 0; } /* 5 2 5 14 2 3 2 3 2 7 1 1 2 2 1 3 */

Compilation message (stderr)

countries.cpp: In function 'int get(int)':
countries.cpp:41:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(p[A]!=A) A=p[A]; return A;
   ^~~~~
countries.cpp:41:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(p[A]!=A) A=p[A]; return A;
                          ^~~~~~
countries.cpp: In function 'int32_t main()':
countries.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i", &n);
   ~~~~~^~~~~~~~~~
countries.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lli%lli%lli", x+l, y+l, s+l);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...