oj.uz

답안 #911355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911355 2024-01-18T19:58:49 Z alexander707070 Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 648608 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const int inf=2e9;

struct point{
    int x,y;
};

bool cmp(point fr,point sc){
    return fr.x<sc.x;
}

struct node{
    int l,r;
    pair<int,int> val;
};

node tree[100*MAXN];

int n,cnt,num,k,zero;
point p[MAXN];

vector< pair<int,int> > w;
map< pair<int,int> ,int> mp;
pair<int,int> ret[MAXN];

priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
pair<int,int> c;

int root[MAXN][2];
/// left <= >
/// right <= >

void add_node(int l,int r){
    num++; 
    tree[num].l=l;
    tree[num].r=r;
}

pair<int,int> combine(pair<int,int> fr,pair<int,int> sc){
    if(fr.first<sc.first)return fr;
    return sc;
}

pair<int,int> getmin(int v,int l,int r,int ll,int rr){
    //cout<<v<<" "<<l<<" "<<r<<"\n";
    if(ll>rr or v==0)return {inf,0};

    if(l==ll and r==rr){
        return tree[v].val;
    }else{
        int tt=(l+r)/2;
        return combine( getmin(tree[v].l,l,tt,ll,min(tt,rr)) , getmin(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
    }
}

int update(int v,int l,int r,int pos,int val){
    //cout<<v<<" "<<l<<" "<<r<<"\n";
    if(l==r){
        add_node(0,0);
        tree[num].val={val,l};
        return num;
    }else{
        int tt=(l+r)/2;

        int id;
        if(pos<=tt){
            id=update(tree[v].l,l,tt,pos,val);
            add_node(id,tree[v].r);
        }else{
            id=update(tree[v].r,tt+1,r,pos,val);
            add_node(tree[v].l,id);
        }

        tree[num].val=combine( tree[tree[num].l].val , tree[tree[num].r].val );
        return num;
    }
}

int mins(int pos){
    int ls=getmin(root[pos][0],1,cnt,1,p[pos].y).first;
    int lg=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first;

    ls+=p[pos].x+ret[p[pos].y].first;
    lg+=p[pos].x-ret[p[pos].y].first;

    return min(ls,lg);
}

void erasemin(int pos){
    int curr=mins(pos),ps;

    if(curr == getmin(root[pos][0],1,cnt,1,p[pos].y).first + p[pos].x + ret[p[pos].y].first ){
        ps=getmin(root[pos][0],1,cnt,1,p[pos].y).second;
        root[pos][0]=update(root[pos][0],1,cnt,ps,inf);
        return;
    }

    if(curr == getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first + p[pos].x - ret[p[pos].y].first ){
        ps=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).second;
        root[pos][1]=update(root[pos][1],1,cnt,ps,inf);
        return;
    }
}

int main(){
    
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
        w.push_back({p[i].y,i});
    }

    sort(w.begin(),w.end()); cnt=1;
    for(int i=0;i<w.size();i++){
        if(i>0 and w[i]!=w[i-1])cnt++;
        mp[w[i]]=cnt; ret[cnt]=w[i];
    }

    for(int i=1;i<=n;i++){
        p[i].y=mp[{p[i].y,i}];
    }

    sort(p+1,p+n+1,cmp);

    for(int i=1;i<=cnt;i++){
        zero=update(zero,1,cnt,i,inf);
    }
    root[0][0]=root[0][1]=zero;

    for(int i=1;i<=n;i++){
        root[i][0]=update(root[i-1][0],1,cnt,p[i].y,-p[i].x-ret[p[i].y].first);
        root[i][1]=update(root[i-1][1],1,cnt,p[i].y,-p[i].x+ret[p[i].y].first);
    }
    for(int i=1;i<=n;i++){
        erasemin(i);
        q.push({mins(i),i});
    }

    for(int i=1;i<=k;i++){
        c=q.top(); q.pop();

        erasemin(c.second);
        q.push({mins(c.second),c.second});

        cout<<c.first<<"\n";
    }

    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 161104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10059 ms 167604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 855 ms 648608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 855 ms 648608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 161104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 161104 KB Output isn't correct
2 Halted 0 ms 0 KB -