Submission #139335

#	Time	Username	Problem	Language	Result	Execution time	Memory
139335		KLPP	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	350 ms	33880 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class DSU{
  int parent[1000000];
  int size[1000000];
public:
  void init(int n){
    rep(i,0,n){
      parent[i]=i;
      size[i]=1;
    }
  }
  int root(int node){
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
  }
  bool merge(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return false;
    if(size[b]>size[a])swap(a,b);
    parent[b]=a;
    size[a]+=size[b];
    return true;
  }
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  s.push_back(1000000001);
  t.push_back(1);
  int n = (int) s.size();
  vector<lld >v;
  rep(i,0,n){
    v.push_back(s[i]);
    v.push_back(t[i]);
  }
  sort(v.begin(),v.end());
  vector<lld> comp;
  rep(i,0,v.size()){
    if(comp.size()==0 || v[i]!=comp[comp.size()-1]){
      comp.push_back(v[i]);
    }
  }
  /*rep(i,0,comp.size())cout<<comp[i]<<" ";
  cout<<endl;*/
  lld edges[n][2];
  lld sections[comp.size()];
  rep(i,0,comp.size())sections[i]=0;
  rep(i,0,n){
    int lo,hi;
    lo=-1;hi=comp.size();
    while(hi-lo>1){
      int mid=(hi+lo)/2;
      if(comp[mid]<=s[i])lo=mid;
      else hi=mid;
    }
    edges[i][0]=lo;
    lo=-1;hi=comp.size();
    while(hi-lo>1){
      int mid=(hi+lo)/2;
      if(comp[mid]<=t[i])lo=mid;
      else hi=mid;
    }
    edges[i][1]=lo;
    rep(j,0,2){
      if(edges[i][j]>0){
	sections[edges[i][j]-1]+=1-2*j;
      }
    }
    //cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
  }
  for(int i=comp.size()-1;i>0;i--){
    sections[i-1]+=sections[i];
  }
  vector<pii> edgelist;
  lld ans=0;
  DSU *D=new DSU();
  D->init(comp.size());
  rep(i,0,comp.size()-1){
    if(sections[i]==0){
      edgelist.push_back(pii(comp[i+1]-comp[i],i));
    }else D->merge(i,i+1);
    
    if(sections[i]<0){
      ans-=(comp[i+1]-comp[i])*sections[i];
    }
  }
  rep(i,0,n){
    D->merge(edges[i][0],edges[i][1]);
  }
  //cout<<ans<<endl;
  sort(edgelist.begin(),edgelist.end());
  rep(i,0,edgelist.size()){
    
    if(D->merge(edgelist[i].second,edgelist[i].second+1)){
      ans+=edgelist[i].first;
    }
  }
  return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:44:7:
   rep(i,0,v.size()){
       ~~~~~~~~~~~~               
railroad.cpp:44:3: note: in expansion of macro 'rep'
   rep(i,0,v.size()){
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:53:7:
   rep(i,0,comp.size())sections[i]=0;
       ~~~~~~~~~~~~~~~            
railroad.cpp:53:3: note: in expansion of macro 'rep'
   rep(i,0,comp.size())sections[i]=0;
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:84:7:
   rep(i,0,comp.size()-1){
       ~~~~~~~~~~~~~~~~~          
railroad.cpp:84:3: note: in expansion of macro 'rep'
   rep(i,0,comp.size()-1){
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:98:7:
   rep(i,0,edgelist.size()){
       ~~~~~~~~~~~~~~~~~~~        
railroad.cpp:98:3: note: in expansion of macro 'rep'
   rep(i,0,edgelist.size()){
   ^~~

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