Submission #992337

#TimeUsernameProblemLanguageResultExecution timeMemory
992337PVM_pvmRoad Construction (JOI21_road_construction)C++17
6 / 100
782 ms8524 KiB
#include<bits/stdc++.h> using namespace std; #define MAXN 250007 struct point { int x,y; } arr[MAXN]; int n,k; bool cmp1(point &a, point &b) { return a.x<b.x; } bool cmp2(point &a, point &b) { return a.y<b.y; } int dist(int a, int b) { int xx=arr[a].x-arr[b].x; if (xx<0) xx*=-1; int yy=arr[a].y-arr[b].y; if (yy<0) yy*=-1; return xx+yy; } priority_queue<int> qu; int BSIZE=1000; void check() { for (int q=0;q<n;q++) { for (int w=1;w<=BSIZE;w++) { if (q-w<0) break; int dst=dist(q,q-w); if (qu.size()<k) qu.push(dst); else { if (dst<qu.top()) { qu.pop(); qu.push(dst); } } } } } int main() { cin>>n>>k; for (int q=0;q<n;q++) cin>>arr[q].x>>arr[q].y; sort(arr,arr+n,cmp1); check(); //sort(arr,arr+n,cmp2); //check(); vector<int> vv; while (!qu.empty()) { vv.push_back(qu.top()); qu.pop(); } reverse(vv.begin(),vv.end()); for (int q=0;q<vv.size();q++) cout<<vv[q]<<"\n"; }

Compilation message (stderr)

road_construction.cpp: In function 'void check()':
road_construction.cpp:35:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |             if (qu.size()<k) qu.push(dst);
      |                 ~~~~~~~~~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int q=0;q<vv.size();q++) cout<<vv[q]<<"\n";
      |                  ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...