Submission #75092

# Submission time Handle Problem Language Result Execution time Memory
75092 2018-09-08T09:46:24 Z cubecube1000 도로 건설 사업 (JOI13_construction) C++14
70 / 100
1821 ms 211040 KB
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const ll MAX=200005;
const ll INFLL=0x3f3f3f3f3f3f3f;
struct vill{
    ll x,y,idx;
};
vill v[MAX];
struct edge{
    ll x,y,d;
    bool operator<(const edge &a)const{
        return d<a.d;
    }
};
struct area{ll x1,y1,x2,y2;};
area h[MAX];
vector<ll> ixcp,iycp,ex[2*MAX],ey[2*MAX],val,val2;
vector<edge> mst;
vector<pll> conn[MAX];
multiset<ll> pos;
ll chk[MAX],n,m,c,par[MAX],cum;
ll x_getidx(ll x){return lower_bound(ixcp.begin(),ixcp.end(),x)-ixcp.begin();}
ll y_getidx(ll y){return lower_bound(iycp.begin(),iycp.end(),y)-iycp.begin();}
ll fnd(ll x){
    if(par[x]!=x) return par[x]=fnd(par[x]);
    return x;
}
void uni(ll x,ll y){
    x=fnd(x), y=fnd(y);
    par[x]=y;
}
bool cmpx(vill a,vill b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmpy(vill a,vill b){
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
ll exist(ll x,ll y){
    set<ll>::iterator it=pos.lower_bound(x+1);
    if(it==pos.end()) return false;
    if(*it<=y-1) return true;
    return false;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&c);
    for(ll i=0;i<n;i++){scanf("%lld%lld",&v[i].x,&v[i].y),v[i].idx=i;}
    for(ll i=0;i<m;i++){scanf("%lld%lld%lld%lld",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
    for(ll i=0;i<m;i++) {
        ixcp.push_back(h[i].x1); ixcp.push_back(h[i].x2);
        iycp.push_back(h[i].y1), iycp.push_back(h[i].y2);
    }
    sort(ixcp.begin(),ixcp.end());
    sort(iycp.begin(),iycp.end());
    for(ll i=0;i<m;i++){
        ex[x_getidx(h[i].x1)].push_back(i), ey[y_getidx(h[i].y1)].push_back(i);
        ex[x_getidx(h[i].x2)].push_back(i), ey[y_getidx(h[i].y2)].push_back(i);
    }
    sort(v,v+n,cmpx);
    for(ll i=1,pt=0;i<n;i++){
        if(v[i-1].x==v[i].x){
            for(;ixcp[pt]<=v[i].x&&pt<ixcp.size();pt++){
                for(ll j=0;j<ex[pt].size();j++) {
                    if(chk[ex[pt][j]]) pos.erase(h[ex[pt][j]].y1),pos.erase(h[ex[pt][j]].y2-1);
                    else pos.insert(h[ex[pt][j]].y1),pos.insert(h[ex[pt][j]].y2-1);
                    chk[ex[pt][j]]^=1;
                }
            }
            if(!exist(v[i-1].y,v[i].y)){
                ll dist=v[i].y-v[i-1].y;
                conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
                conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
            }
        }
    }
    pos.clear();
    for(ll i=0;i<m;i++) chk[i]=0;
    sort(v,v+n,cmpy);
    for(ll i=1,pt=0;i<n;i++){
        if(v[i-1].y==v[i].y){
            for(;iycp[pt]<=v[i].y&&pt<iycp.size();pt++){
                for(ll j=0;j<ey[pt].size();j++) {
                    if(chk[ey[pt][j]]) pos.erase(h[ey[pt][j]].x1),pos.erase(h[ey[pt][j]].x2-1);
                    else pos.insert(h[ey[pt][j]].x1),pos.insert(h[ey[pt][j]].x2-1);
                    chk[ey[pt][j]]^=1;
                }
            }
            if(!exist(v[i-1].x,v[i].x)){
                ll dist=v[i].x-v[i-1].x;
                conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
                conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
            }
        }
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<conn[i].size();j++) {
            if(i<conn[i][j].x) mst.push_back({i,conn[i][j].x,conn[i][j].y});
            //printf("%lld%lld%lld\n",i,conn[i][j].x,conn[i][j].y);
        }
    }

    for(ll i=0;i<n;i++) par[i]=i;
    sort(mst.begin(),mst.end());
    val.push_back(0),val2.push_back(0);
    for(ll i=0;i<mst.size();i++){
        if(fnd(mst[i].x)!=fnd(mst[i].y)) cum+=mst[i].d, val.push_back(cum), val2.push_back(mst[i].d), uni(mst[i].x,mst[i].y);
    }

    vector<ll>::iterator it;
    for(ll i=0;i<c;i++){
        ll t1,t2;
        scanf("%lld%lld",&t1,&t2);
        if(n-val.size()>=t2){
            printf("-1\n");
        }
        else{
            it=lower_bound(val2.begin(),val2.end(),t1);
            ll idx=max((ll)(it-val2.begin()-1),n-t2);
            printf("%lld\n",val[idx]+t1*(n-idx));
        }
    }
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:68:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;ixcp[pt]<=v[i].x&&pt<ixcp.size();pt++){
                                    ~~^~~~~~~~~~~~
construction.cpp:69:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(ll j=0;j<ex[pt].size();j++) {
                            ~^~~~~~~~~~~~~~
construction.cpp:87:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;iycp[pt]<=v[i].y&&pt<iycp.size();pt++){
                                    ~~^~~~~~~~~~~~
construction.cpp:88:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(ll j=0;j<ey[pt].size();j++) {
                            ~^~~~~~~~~~~~~~
construction.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j=0;j<conn[i].size();j++) {
                    ~^~~~~~~~~~~~~~~
construction.cpp:111:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<mst.size();i++){
                ~^~~~~~~~~~~
construction.cpp:119:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(n-val.size()>=t2){
            ~~~~~~~~~~~~^~~~
construction.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&m,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:53:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=0;i<n;i++){scanf("%lld%lld",&v[i].x,&v[i].y),v[i].idx=i;}
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
construction.cpp:54:96: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=0;i<m;i++){scanf("%lld%lld%lld%lld",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
construction.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 47 ms 25464 KB Output is correct
2 Correct 262 ms 44792 KB Output is correct
3 Correct 272 ms 48860 KB Output is correct
4 Correct 413 ms 71028 KB Output is correct
5 Correct 350 ms 71028 KB Output is correct
6 Correct 274 ms 71028 KB Output is correct
7 Correct 276 ms 76692 KB Output is correct
8 Correct 301 ms 76692 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1647 ms 91972 KB Output is correct
2 Correct 1623 ms 103416 KB Output is correct
3 Correct 1572 ms 109248 KB Output is correct
4 Correct 1584 ms 120720 KB Output is correct
5 Incorrect 1010 ms 120720 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 581 ms 120720 KB Output is correct
2 Correct 600 ms 120720 KB Output is correct
3 Correct 596 ms 120720 KB Output is correct
4 Correct 679 ms 137320 KB Output is correct
5 Correct 446 ms 137320 KB Output is correct
6 Correct 674 ms 137320 KB Output is correct
7 Correct 599 ms 137320 KB Output is correct
8 Correct 566 ms 137320 KB Output is correct
9 Correct 537 ms 137784 KB Output is correct
10 Correct 587 ms 137784 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1801 ms 163680 KB Output is correct
2 Correct 991 ms 163680 KB Output is correct
3 Correct 1762 ms 163680 KB Output is correct
4 Correct 422 ms 163680 KB Output is correct
5 Correct 1762 ms 163680 KB Output is correct
6 Correct 435 ms 163680 KB Output is correct
7 Correct 1587 ms 163680 KB Output is correct
8 Correct 1821 ms 163680 KB Output is correct
9 Correct 910 ms 190136 KB Output is correct
10 Correct 1173 ms 211040 KB Output is correct
11 Correct 623 ms 211040 KB Output is correct