oj.uz

Submission #73162

# Submission time Handle Problem Language Result Execution time Memory
73162 2018-08-28T01:48:45 Z Kmcode Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 1819 ms 55592 KB 
#pragma GCC optimize (3)
#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;
	}
	
	//if(clock()/(double)(CLOCKS_PER_SEC)<0.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:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
railroad.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
               ~^~~~~~~~~
railroad.cpp:61: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 4 ms 2296 KB n = 2
2 Correct 4 ms 2336 KB n = 2
3 Correct 4 ms 2360 KB n = 2
4 Correct 4 ms 2408 KB n = 2
5 Correct 4 ms 2432 KB n = 2
6 Incorrect 3 ms 2460 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 4 ms 2296 KB n = 2
2 Correct 4 ms 2336 KB n = 2
3 Correct 4 ms 2360 KB n = 2
4 Correct 4 ms 2408 KB n = 2
5 Correct 4 ms 2432 KB n = 2
6 Incorrect 3 ms 2460 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 1730 ms 49532 KB n = 199999
2 Correct 1523 ms 49584 KB n = 199991
3 Correct 1591 ms 49660 KB n = 199993
4 Correct 1324 ms 49660 KB n = 152076
5 Correct 722 ms 49660 KB n = 93249
6 Correct 1539 ms 49660 KB n = 199910
7 Correct 1444 ms 49660 KB n = 199999
8 Correct 1402 ms 49660 KB n = 199997
9 Correct 1718 ms 49660 KB n = 171294
10 Correct 1296 ms 49660 KB n = 140872
11 Correct 1521 ms 49660 KB n = 199886
12 Correct 1360 ms 49660 KB n = 199996
13 Correct 1259 ms 49660 KB n = 200000
14 Correct 1197 ms 49660 KB n = 199998
15 Correct 1072 ms 49660 KB n = 200000
16 Correct 1187 ms 49660 KB n = 199998
17 Correct 1382 ms 49660 KB n = 200000
18 Correct 1188 ms 49660 KB n = 190000
19 Correct 1377 ms 49660 KB n = 177777
20 Correct 652 ms 49660 KB n = 100000
21 Correct 1584 ms 49744 KB n = 200000
22 Correct 1662 ms 55592 KB n = 200000
23 Correct 1819 ms 55592 KB n = 200000

Subtask #4
0 / 36.0

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