Submission #813455

#	Time	Username	Problem	Language	Result	Execution time	Memory
813455		mosiashvililuka	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	628 ms	45772 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
long long pas,A,B;
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,tt;
//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){
            c=(*it).first;
            tt=it;tt++;d=(*tt).first;
            edges.push_back({{m[c],m[c]+1},0});
          	A=zx-1;B=(d-c);
            pas+=A*B;
            //cout<<zx<<"   "<<p[pi].first<<" "<<p[pi-1].first<<"  "<<(*it).first<<"\n";
        }
    }
    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;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36