| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 874527 | Lib | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
int n;
vector <pair <int,int> > EnterSpeed;
vector <pair <int,int> > ExitSpeed;
int AlreadyConnected[200003];
long long plan_roller_coaster (vector <int> s, vector <int> t){
n=s.size();
EnterSpeed.clear();
ExitSpeed.clear();
/*
Subtask 1 and 2 is trival and basically not worth spending time for, so I'll skip it
Of course, there exists a better solution to subtask 3 that is actually relevant to the full solution, but 30 points is 30 points,
especially if that's from a shitty greedy solution
*/
/*
If a finished track could be created without adding in any additional segments, this is the equivalent of: for all but 1 segment, there
has to be a track segment that follows it.
=> Just greedily assign exit speeds with corresponding entrance speeds that isn't from the same segment,
if n-1 pairs (or more) could be formed, there exists an answer.
Simple as that.
*/
for(int i=0;i<n;i++){
EnterSpeed.push_back({s[i],i});
ExitSpeed.push_back({t[i],i});
}
sort(EnterSpeed.begin(),EnterSpeed.end(),greater<pair <int,int> >());
sort(ExitSpeed.begin(),ExitSpeed.end(),greater<pair <int,int> >());
int ValidPairs=0;
pair <int,int> temp;
//Assigning track endpoints with new tracks
while(!EnterSpeed.empty()&&!ExitSpeed.empty()&&ValidPairs<n-1){
//Trying to match with the startpoint that isn't in the same track, and has the smallest entrance speed possible
while(!EnterSpeed.empty()&&ExitSpeed.back().first>EnterSpeed.back().first||ALreadyConnected[EnterSpeed.back().second]){
EnterSpeed.pop_back();
}
//It matches and doesn't belong to the same sector. Is valid, so increase the amount of matched pairs by 1
if(!EnterSpeed.empty()&&ExitSpeed.back().second!=EnterSpeed.back().second){
ValidPairs++;
AlreadyConnected[ExitSpeed.back().second]=1;
EnterSpeed.pop_back();
ExitSpeed.pop_back();
}else if(EnterSpeed.size()>1){
//It matches, but both of this startpoint and endpoint belongs in the same segment. Match it with the
//next smallest unmatched entrance speed
temp=EnterSpeed.back();
EnterSpeed.pop_back();
while(!EnterSpeed.empty()&&AlreadyConnected[EnterSpeed.back().second]){
EnterSpeed.pop_back();
}
if(EnterSpeed.empty()){
break;
}
AlreadyConnected[ExitSpeed.back().second]=1;
EnterSpeed.pop_back();
ExitSpeed.pop_back();
ValidPairs++;
EnterSpeed.push_back(temp);
}else{
//If you can't find any other segment and ran into a conflict, all is lost and done. Stop the assigning
//process immediately and hope for the best
break;
}
}
//If at least N-1 pairs could be matched, there exists 1 valid rollercoaster using only the default tracks. Otherwise, no
return (ValidPairs<n-1);
}