Submission #74844

#TimeUsernameProblemLanguageResultExecution timeMemory
74844cubecube1000도로 건설 사업 (JOI13_construction)C++14
0 / 100
1422 ms154316 KiB
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef unsigned long long ll; typedef pair<int,int> pii; typedef pair<ll, ll> pll; const int MAX=1<<18; const ll INFLL=0x3f3f3f3f3f3f3f; struct vill{ int x,y,idx; }; vill v[MAX]; struct edge{ int x,y,d; bool operator<(const edge &a)const{ return d<a.d; } }; struct area{int x1,y1,x2,y2;}; area h[MAX]; vector<int> ixcp,iycp,ex[MAX],ey[MAX],val2; vector<edge> mst; vector<pii> conn[MAX]; map<int,int> xcp,ycp; multiset<int> pos; vector<pii> ch; vector<ll> val; int chk[MAX],n,m,c,par[MAX]; ll cum; int fnd(int x){ if(par[x]!=x) return par[x]=fnd(par[x]); return x; } void uni(int x,int 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; } bool cmpidx(vill a,vill b){ return a.idx<b.idx; } int exist(int x,int y){ set<int>::iterator it=pos.lower_bound(x); if(it==pos.end()) return false; if(*it<=y) return true; return false; } int main(){ scanf("%d%d%d",&n,&m,&c); for(int i=0;i<n;i++){scanf("%d%d",&v[i].x,&v[i].y),v[i].idx=i;} for(int i=0;i<m;i++){scanf("%d%d%d%d",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;} for(int i=0;i<n;i++) { if(xcp.find(h[i].x1)==xcp.end()) ixcp.push_back(h[i].x1), xcp[h[i].x1]=0; if(xcp.find(h[i].x2)==xcp.end()) ixcp.push_back(h[i].x2), xcp[h[i].x2]=0; if(ycp.find(h[i].y1)==ycp.end()) iycp.push_back(h[i].y1), ycp[h[i].y1]=0; if(ycp.find(h[i].y2)==ycp.end()) iycp.push_back(h[i].y2), ycp[h[i].y2]=0; } sort(ixcp.begin(),ixcp.end()); sort(iycp.begin(),iycp.end()); for(int i=0;i<ixcp.size();i++) xcp[ixcp[i]]=i; for(int i=0;i<iycp.size();i++) ycp[iycp[i]]=i; for(int i=0;i<m;i++){ ex[xcp[h[i].x1]].push_back(i), ey[ycp[h[i].y1]].push_back(i); ex[xcp[h[i].x2]].push_back(i), ey[ycp[h[i].y2]].push_back(i); } sort(v,v+n,cmpx); for(int 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(int 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)){ int 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(int i=0;i<m;i++) chk[i]=0; sort(v,v+n,cmpy); for(int 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(int 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; } } //printf("%d %d %d\n",pos.size(),v[i].y,iycp.size()); if(!exist(v[i-1].x,v[i].x)){ int 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(int i=0;i<n;i++){ for(int 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("%d %d %d\n",i,conn[i][j].x,conn[i][j].y); } } for(int i=0;i<n;i++) par[i]=i; sort(mst.begin(),mst.end()); val.push_back(0ll),val2.push_back(0); for(int i=0;i<mst.size();i++){ if(fnd(mst[i].x)!=fnd(mst[i].y)) cum+=(ll)mst[i].d, val.push_back(cum), val2.push_back(mst[i].d), uni(mst[i].x,mst[i].y); } vector<int>::iterator it; for(int i=0;i<c;i++){ int t1,t2; scanf("%d%d",&t1,&t2); if(n-val.size()>=t2){ printf("-1\n"); } else{ it=lower_bound(val2.begin(),val2.end(),t1); int idx=max((int)(it-val2.begin())-1,n-t2); printf("%lld\n",(ll)val[idx]+t1*(n-idx)); } } }

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ixcp.size();i++) xcp[ixcp[i]]=i;
                 ~^~~~~~~~~~~~
construction.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<iycp.size();i++) ycp[iycp[i]]=i;
                 ~^~~~~~~~~~~~
construction.cpp:77:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;ixcp[pt]<=v[i].x&&pt<ixcp.size();pt++){
                                    ~~^~~~~~~~~~~~
construction.cpp:78:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<ex[pt].size();j++) {
                             ~^~~~~~~~~~~~~~
construction.cpp:96:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;iycp[pt]<=v[i].y&&pt<iycp.size();pt++){
                                    ~~^~~~~~~~~~~~
construction.cpp:97:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<ey[pt].size();j++) {
                             ~^~~~~~~~~~~~~~
construction.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<conn[i].size();j++) {
                     ~^~~~~~~~~~~~~~~
construction.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<mst.size();i++){
                 ~^~~~~~~~~~~
construction.cpp:128:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(n-val.size()>=t2){
            ~~~~~~~~~~~~^~~~
construction.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~~
construction.cpp:58:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++){scanf("%d%d",&v[i].x,&v[i].y),v[i].idx=i;}
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
construction.cpp:59:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<m;i++){scanf("%d%d%d%d",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
construction.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...