Submission #114676

#	Time	Username	Problem	Language	Result	Execution time	Memory
114676		KLPP	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	294 ms	57716 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
vector<int> nei[1000000];
bool visited[1000000];
int absol(int a){
  if(a>0)return a;
  return -a;
}
int sign(int a){
  if(a>0)return 0;
  return 1;
}
void DFS(int node){
  visited[node]=true;
  trav(v,nei[node]){
    if(!visited[v])DFS(v);
  }
}
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<pii >v;
  rep(i,0,n){
    //cout<<s[i]<<" "<<t[i]<<endl;
    v.push_back(pii(s[i],+i+1));
    v.push_back(pii(t[i],-i-1));
  }
  sort(v.begin(),v.end());
  int imbalance=0;
  rep(i,0,v.size()){
    if(v[i].second<0)imbalance++;
    else imbalance--;
    if(imbalance<0)return 1;
    if(imbalance>0){
      nei[i].push_back(i+1);
    }
  }
  int index[n][2];
  rep(i,0,v.size()){
    //cout<<v[i].first<<" "<<v[i].second<<endl;
    index[absol(v[i].second)-1][sign(v[i].second)]=i;
  }
  rep(i,0,n){
    //cout<<index[i][0]<<" "<<index[i][1]<<endl;
    nei[index[i][0]].push_back(index[i][1]);
  }
  /*rep(i,0,v.size()-1){
    nei[i].push_back(i+1);
  }*/
  rep(i,0,v.size())visited[i]=false;
  DFS(0);
  rep(i,0,v.size()){
    //cout<<visited[i]<<endl;
    if(!visited[i])return 1;
  }
  return 0;
}

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:36:7:
   rep(i,0,v.size()){
       ~~~~~~~~~~~~               
railroad.cpp:36: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:45:7:
   rep(i,0,v.size()){
       ~~~~~~~~~~~~               
railroad.cpp:45: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:56:7:
   rep(i,0,v.size())visited[i]=false;
       ~~~~~~~~~~~~               
railroad.cpp:56:3: note: in expansion of macro 'rep'
   rep(i,0,v.size())visited[i]=false;
   ^~~
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:58:7:
   rep(i,0,v.size()){
       ~~~~~~~~~~~~               
railroad.cpp:58:3: note: in expansion of macro 'rep'
   rep(i,0,v.size()){
   ^~~

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