Submission #73148

#	Time	Username	Problem	Language	Result	Execution time	Memory
73148		Kmcode	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	1061 ms	96296 KiB

railroad

#include<bits/stdc++.h>
using namespace std;

//#include "railroad.h"

map<int,long long int> mp;

#define MAX 200002
int belong[MAX];
inline int root(int b){
	if(belong[b]==-1){
		return b;
	}
	return belong[b]=root(belong[b]);
}
void merge(int a,int b){
	a=root(a);
	b=root(b);
	if(a==b)return;
	belong[a]=b;
	return;
}
map<int,int> idx;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	memset(belong,-1,sizeof(belong));
	t.push_back(-1);
	s.push_back(INT_MAX-3);
    for(int i=0;i<s.size();i++){
		mp[s[i]]++;
		mp[t[i]]--;
		idx[s[i]]=0;
		idx[t[i]]=0;
	}
	int ii=-1;
	for(auto &it:idx){
		ii++;
		it.second=ii;
	}
	for(int i=0;i<s.size();i++){
		merge(idx[s[i]],idx[t[i]]);
	}
	long long int sum=0;
	for(auto &it:mp){
		if(sum)merge(idx[it.first],idx[it.first]-1);
		long long int add=sum;
		sum-=it.second;
		it.second-=add;
		it.second+=sum;
		//cout<<add<<" "<<sum<<endl;
		if(sum<0){
			return 111;
		}
	}
	set<int> ss;
	for(int i=0;i<mp.size();i++){
		ss.insert(root(i));
	}
	if(ss.size()>1){
		return 333;
	}
	for(auto it:mp){
		if(it.second!=0){
			return 222;
		}
	}
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
railroad.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
railroad.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<mp.size();i++){
              ~^~~~~~~~~~

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