제출 #813439

#제출 시각아이디문제언어결과실행 시간메모리
813439mosiashvililukaRoller Coaster Railroad (IOI16_railroad)C++14
30 / 100
643 ms42276 KiB
#include<bits/stdc++.h> #include "railroad.h" using namespace std; long long pas; int a,b,c,d,e,i,j,ii,jj,zx,xc,S[200009],T[200009],pi,msh[400009],zm[400009],cmp; pair <int, int> p[400009]; map <int, int> m; map <int, int>::iterator it; //vector <int> v[400009]; vector <pair <pair <int, int>, int> > edges; int fnd(int q){ if(msh[q]==q) return q; else return msh[q]=fnd(msh[q]); } void mrg(int q, int w){ q=fnd(q);w=fnd(w); if(q==w) return; cmp--; if(zm[q]<zm[w]) swap(q,w); if(zm[q]==zm[w]) zm[q]++; msh[w]=q; } long long plan_roller_coaster(std::vector<int> Ss, std::vector<int> Tt) { a=Ss.size(); for(i=1; i<=a; i++){ S[i]=Ss[i-1];T[i]=Tt[i-1]; } for(i=1; i<=a; i++){ m[S[i]]++;m[T[i]]--; } zx=0;xc=0; pi++;p[pi]={0,0}; xc++;m[0]=xc; for(it=m.begin(); it!=m.end(); it++){ if((*it).first==0) continue; zx+=(*it).second; pi++;p[pi]={(*it).first,zx}; xc++; (*it).second=xc; if(zx>1){ edges.push_back({{m[p[pi-1].first],m[p[pi].first]},0}); pas+=zx-1; } } pi++;p[pi]={1000000003,zx}; xc++;m[p[pi].first]=xc; for(ii=1; ii<pi; ii++){ if(p[ii].second<1){ /*v[m[p[ii].first]].push_back(m[p[ii+1].first]); v[m[p[ii+1].first]].push_back(m[p[ii].first]);*/ edges.push_back({{m[p[ii].first],m[p[ii+1].first]},0}); } } for(i=1; i<=a; i++){ /*v[m[S[i]]].push_back(m[T[i]]); v[m[T[i]]].push_back(m[S[i]]);*/ edges.push_back({{m[S[i]],m[T[i]]},0}); } /*dfs(1); if(raod!=pi) return 1;*/ for(ii=1; ii<pi; ii++){ edges.push_back({{m[p[ii].first],m[p[ii+1].first]},p[ii+1].first-p[ii].first}); } for(auto &x:edges){ swap(x.first.first,x.second); } sort(edges.begin(),edges.end()); for(auto &x:edges){ swap(x.first.first,x.second); } for(i=1; i<=pi; i++){ msh[i]=i;zm[i]=0; } cmp=pi; //cout<<pas<<"\n"; for(auto x:edges){ if(cmp==1) break; //cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<" :"; if(fnd(x.first.first)==fnd(x.first.second)) continue; mrg(x.first.first,x.first.second); //cout<<cmp<<"\n"; pas+=x.second; } return pas; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...