oj.uz

Submission #205192

# Submission time Handle Problem Language Result Execution time Memory
205192 2020-02-28T09:34:16 Z puppies_and_rainbows Roller Coaster Railroad (IOI16_railroad) C++14
0 / 100
 137 ms 15216 KB 
#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

pair<long long, long long> a[200005], b[200005];
long long f[200005], n, tot;

long long find(long long i)
{
	return f[i]==i? f[i]:f[i]=find(f[i]);
}

void unionn(long long i, long long j)
{
	f[find(i)]=find(j);
	tot--;
}

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
	s.push_back(1000000000);
	t.push_back(1);
	n=s.size(), tot=n;
	for(long long i=1; i<=n; i++)
	{
		f[i]=i;
		a[i]={s[i-1], i};
		b[i]={t[i-1], i};
	}
	sort(a+1, a+n+1);
	sort(b+1, b+n+1);
	for(long long i=1; i<=n; i++)
	{
		if(a[i].first<b[i].first) return 1;
		unionn(a[i].second, b[i].second);
	}
	for(long long i=1; i<n; i++)
	{
		if(find(a[i].second)!=find(a[i+1].second))
		{
			if(a[i].first>b[i+1].first)
			{
				unionn(a[i].second, a[i+1].second);
			}
		}
	}
	if(tot==1) return 0;
	else return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB answer is not correct: 1 instead of 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB answer is not correct: 1 instead of 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 15216 KB answer is not correct: 1 instead of 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB answer is not correct: 1 instead of 0
2 Halted 0 ms 0 KB -