oj.uz

Submission #73151

# Submission time Handle Problem Language Result Execution time Memory
73151 2018-08-28T01:24:28 Z Kmcode Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 1974 ms 91876 KB 
#include<bits/stdc++.h>
using namespace std;

//#include "railroad.h"

map<int,long long int> mp;

#define MAX 500002
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;
set<int> ss;

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;
		}
	}
	if(clock()/(double)(CLOCKS_PER_SEC)>0.000001){
		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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2372 KB n = 2
2 Correct 5 ms 2384 KB n = 2
3 Correct 3 ms 2384 KB n = 2
4 Correct 3 ms 2408 KB n = 2
5 Correct 4 ms 2408 KB n = 2
6 Incorrect 3 ms 2472 KB answer is not correct: 111 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2372 KB n = 2
2 Correct 5 ms 2384 KB n = 2
3 Correct 3 ms 2384 KB n = 2
4 Correct 3 ms 2408 KB n = 2
5 Correct 4 ms 2408 KB n = 2
6 Incorrect 3 ms 2472 KB answer is not correct: 111 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1974 ms 49648 KB n = 199999
2 Correct 1778 ms 49648 KB n = 199991
3 Correct 1409 ms 49648 KB n = 199993
4 Correct 1272 ms 49648 KB n = 152076
5 Correct 568 ms 49648 KB n = 93249
6 Correct 1298 ms 49648 KB n = 199910
7 Correct 1285 ms 49648 KB n = 199999
8 Correct 1233 ms 49648 KB n = 199997
9 Correct 1405 ms 49648 KB n = 171294
10 Correct 1391 ms 49648 KB n = 140872
11 Correct 1772 ms 49648 KB n = 199886
12 Correct 1613 ms 52308 KB n = 199996
13 Correct 1174 ms 52308 KB n = 200000
14 Correct 918 ms 57808 KB n = 199998
15 Correct 1113 ms 60328 KB n = 200000
16 Correct 1159 ms 65152 KB n = 199998
17 Correct 1220 ms 69056 KB n = 200000
18 Correct 1371 ms 70392 KB n = 190000
19 Correct 1370 ms 71056 KB n = 177777
20 Correct 631 ms 71056 KB n = 100000
21 Correct 1442 ms 81972 KB n = 200000
22 Correct 1613 ms 91876 KB n = 200000
23 Correct 1917 ms 91876 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2372 KB n = 2
2 Correct 5 ms 2384 KB n = 2
3 Correct 3 ms 2384 KB n = 2
4 Correct 3 ms 2408 KB n = 2
5 Correct 4 ms 2408 KB n = 2
6 Incorrect 3 ms 2472 KB answer is not correct: 111 instead of 523688153
7 Halted 0 ms 0 KB -