oj.uz

Submission #413647

# Submission time Handle Problem Language Result Execution time Memory
413647 2021-05-29T07:47:53 Z Ronin13 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 352392 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
using namespace std;

struct Point{
    ll x,y;
    Point(ll x,ll y):x(x),y(y){}
    Point(){
    }
};

ll dist(Point A,Point B){
    return abs(A.x-B.x)+abs(A.y-B.y);
}

bool check(vector<Point>a){
    for(Point A:a){
        if(A.y!=0)return false;
    }
    return true;
}
bool comp(Point A,Point B){
    if(A.x==B.x)return A.y<B.y;
    return A.x<B.x;
}
void solve(){
    int n;cin>>n;
    int k;cin>>k;
    vector<Point>a(n);
    for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;
    sort(a.begin(),a.end(),comp);
    if(check(a)){
        multiset<pair<ll,pii> >d;
        for(int i=0;i<n-1;i++)d.insert({dist(a[i],a[i+1]),{i,i+1}});
        vector<ll>ans;
        while(ans.size()<k){
            pair<ll,pii>x=*d.begin();
            ans.pb(x.f);
            int l=x.s.f,r=x.s.s;
            d.erase(x);
            if(r<n-1)
            d.insert({dist(a[l],a[r+1]),{l,r+1}});
        }
        for(ll to:ans){
            cout<<to<<"\n";
        }
        return;
    }
    multiset<ll>d;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            d.insert(dist(a[i],a[j]));
        }
    }
    int ind=0;
    for(ll to:d){
            if(ind>=k)break;
            cout<<to<<"\n";
            ind++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

road_construction.cpp: In function 'void solve()':
road_construction.cpp:43:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         while(ans.size()<k){
      |               ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 26320 KB Output is correct
2 Correct 436 ms 26384 KB Output is correct
3 Correct 163 ms 14660 KB Output is correct
4 Correct 163 ms 14712 KB Output is correct
5 Correct 329 ms 25220 KB Output is correct
6 Correct 174 ms 23760 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 25080 KB Output is correct
2 Correct 564 ms 25048 KB Output is correct
3 Correct 79 ms 4912 KB Output is correct
4 Correct 265 ms 28024 KB Output is correct
5 Correct 317 ms 28012 KB Output is correct
6 Correct 330 ms 28116 KB Output is correct
7 Correct 303 ms 27468 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10102 ms 350184 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 10102 ms 350184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 26320 KB Output is correct
2 Correct 436 ms 26384 KB Output is correct
3 Correct 163 ms 14660 KB Output is correct
4 Correct 163 ms 14712 KB Output is correct
5 Correct 329 ms 25220 KB Output is correct
6 Correct 174 ms 23760 KB Output is correct
7 Execution timed out 10055 ms 352392 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 26320 KB Output is correct
2 Correct 436 ms 26384 KB Output is correct
3 Correct 163 ms 14660 KB Output is correct
4 Correct 163 ms 14712 KB Output is correct
5 Correct 329 ms 25220 KB Output is correct
6 Correct 174 ms 23760 KB Output is correct
7 Correct 520 ms 25080 KB Output is correct
8 Correct 564 ms 25048 KB Output is correct
9 Correct 79 ms 4912 KB Output is correct
10 Correct 265 ms 28024 KB Output is correct
11 Correct 317 ms 28012 KB Output is correct
12 Correct 330 ms 28116 KB Output is correct
13 Correct 303 ms 27468 KB Output is correct
14 Execution timed out 10102 ms 350184 KB Time limit exceeded
15 Halted 0 ms 0 KB -