oj.uz

Submission #992353

# Submission time Handle Problem Language Result Execution time Memory
992353 2024-06-04T09:59:31 Z Brinyon Road Construction (JOI21_road_construction) C++14
32 / 100
 10000 ms 8712 KB 
#include<bits/stdc++.h>
#define MAXN 250001
using namespace std;
struct point{
    long long x,y;
};
long long dist(point a,point b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}
long long n,k;
point a[MAXN];
bool cmp(point a,point b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
priority_queue<long long> pq;
int main(){
    cin>>n>>k;
    for(long long i=0;i<n;i++){
        long long x,y;
        cin>>a[i].x>>a[i].y;
    }
    sort(a,a+n,cmp);
    for(long long i=0;i<n;i++){
        for(long long i1=i-1;i1>=0;i1--){
            long long dst=dist(a[i],a[i1]);
            if(pq.size()<k) pq.push(dst);
            else if(dst<pq.top()){
                pq.push(dst);
                pq.pop();
            }
        }
    }
    vector<long long> v;
    while(!pq.empty()){
        v.push_back(pq.top());
        pq.pop();
    }
    for(long long i=v.size()-1;i>=0;i--){
        cout<<v[i]<<"\n";
    }
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:20:19: warning: unused variable 'x' [-Wunused-variable]
   20 |         long long x,y;
      |                   ^
road_construction.cpp:20:21: warning: unused variable 'y' [-Wunused-variable]
   20 |         long long x,y;
      |                     ^
road_construction.cpp:27:25: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |             if(pq.size()<k) pq.push(dst);
      |                ~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6976 KB Output is correct
2 Correct 63 ms 6844 KB Output is correct
3 Correct 47 ms 6912 KB Output is correct
4 Correct 45 ms 6976 KB Output is correct
5 Correct 65 ms 5900 KB Output is correct
6 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10013 ms 6344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10048 ms 4180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10048 ms 4180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6976 KB Output is correct
2 Correct 63 ms 6844 KB Output is correct
3 Correct 47 ms 6912 KB Output is correct
4 Correct 45 ms 6976 KB Output is correct
5 Correct 65 ms 5900 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 7172 ms 8712 KB Output is correct
8 Correct 7299 ms 8712 KB Output is correct
9 Correct 45 ms 6972 KB Output is correct
10 Correct 7341 ms 7944 KB Output is correct
11 Correct 7477 ms 7744 KB Output is correct
12 Correct 7012 ms 8512 KB Output is correct
13 Correct 7183 ms 7556 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6976 KB Output is correct
2 Correct 63 ms 6844 KB Output is correct
3 Correct 47 ms 6912 KB Output is correct
4 Correct 45 ms 6976 KB Output is correct
5 Correct 65 ms 5900 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Execution timed out 10013 ms 6344 KB Time limit exceeded
8 Halted 0 ms 0 KB -