Submission #226603

#TimeUsernameProblemLanguageResultExecution timeMemory
226603MKopchevCountries (BOI06_countries)C++14
100 / 100
7 ms512 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=1e3+42; struct city { int x,y,strength; }; city inp[nmax]; int n; int dist(city a,city b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int score(city i,city best,city current) { pair<int,int> u={best.strength,dist(i,best)}; pair<int,int> v={current.strength,dist(i,current)}; if(i.strength*v.second>=v.first)return -1; if(u.first*v.second<u.second*v.first)return 1; if(u.first*v.second==u.second*v.first)return 0; return -1; } int parent[nmax]; int main() { scanf("%i",&n); for(int i=1;i<=n;i++) scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].strength); inp[0].strength=-1; for(int i=1;i<=n;i++) { int best=0,cnt=1; for(int j=1;j<=n;j++) if(j!=i) { int type=score(inp[i],inp[best],inp[j]); if(type==1)best=j,cnt=1; else if(type==0)cnt++; } if(best==0)parent[i]=-1; else if(cnt==1)parent[i]=best; else parent[i]=0; } for(int i=1;i<=n;i++) { int best=parent[i]; if(parent[i]>0) { while(parent[best]>0)best=parent[best]; } if(parent[i]==-1)printf("K\n"); else if(parent[i])printf("%i\n",best); else printf("D\n"); } return 0; }

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
countries.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].strength);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...