Submission #813411

#	Time	Username	Problem	Language	Result	Execution time	Memory
813411		mosiashvililuka	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	743 ms	66792 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,S[200009],T[200009],pi,bo[400009],raod;
pair <int, int> p[400009];
map <int, int> m;
map <int, int>::iterator it;
vector <int> v[400009];
void dfs(int q){
    bo[q]=1;raod++;
    for(auto x:v[q]){
        if(bo[x]==1) continue;
        dfs(x);
    }
}
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) return 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]);
        }
    }

    for(i=1; i<=a; i++){
        v[m[S[i]]].push_back(m[T[i]]);
        v[m[T[i]]].push_back(m[S[i]]);
    }
    dfs(1);
    if(raod!=pi) return 1;
    return 0;
}

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