#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
lint D[1<<16][16];
int v[200002];
int line[200002],to[200002],rev[200002],sT[200002],num[200002],col;
void dfs(int p)
{
v[p]=col;
if(!v[sT[to[p]]])dfs(sT[to[p]]);
}
lint plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
int ch=0;
vector<pii>S;
vector<pii>T;
for(int i=0;i<n;i++)S.push_back({s[i],i});
for(int i=0;i<n;i++)T.push_back({t[i],i});
S.push_back({1e9+1,n});T.push_back({0,n});
sort(S.begin(),S.end());
sort(T.begin(),T.end());
for(int i=0;i<=n;i++)num[T[i].second]=i;
int j=0;
for(int i=0;i<=n;i++)
{
while(j<=n && T[i].first>S[j].first)j++;
line[i]=j;
if(j>i)
{
return 1;
}
to[i]=i;rev[i]=i;
sT[i]=num[S[i].second];
}
col=0;
for(int i=0;i<=n;i++)
{
if(!v[i])
{
col++;
dfs(i);
}
}
int real[200002];
for(int i=1;i<=col;i++)real[i]=i;
for(int i=0;i<=n;i++)
{
if(real[v[line[i]]]!=real[v[i]])
{
real[v[i]]=real[v[line[i]]]=min(real[v[i]],real[v[line[i]]]);
}
}
for(int i=1;i<=col;i++)if(real[i]!=1)return 1;
return 0;
}
Compilation message
railroad.cpp: In function 'lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:20:9: warning: unused variable 'ch' [-Wunused-variable]
20 | int ch=0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1108 KB |
n = 2 |
5 |
Correct |
1 ms |
1108 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1108 KB |
n = 2 |
5 |
Correct |
1 ms |
1108 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
12092 KB |
n = 199999 |
2 |
Correct |
85 ms |
8832 KB |
n = 199991 |
3 |
Correct |
79 ms |
8776 KB |
n = 199993 |
4 |
Correct |
76 ms |
9672 KB |
n = 152076 |
5 |
Correct |
39 ms |
6288 KB |
n = 93249 |
6 |
Correct |
76 ms |
12100 KB |
n = 199910 |
7 |
Correct |
81 ms |
12100 KB |
n = 199999 |
8 |
Correct |
80 ms |
12100 KB |
n = 199997 |
9 |
Correct |
87 ms |
10564 KB |
n = 171294 |
10 |
Correct |
67 ms |
8936 KB |
n = 140872 |
11 |
Correct |
84 ms |
12104 KB |
n = 199886 |
12 |
Correct |
84 ms |
12088 KB |
n = 199996 |
13 |
Correct |
87 ms |
12100 KB |
n = 200000 |
14 |
Correct |
92 ms |
8776 KB |
n = 199998 |
15 |
Correct |
79 ms |
8892 KB |
n = 200000 |
16 |
Correct |
76 ms |
8768 KB |
n = 199998 |
17 |
Correct |
77 ms |
8772 KB |
n = 200000 |
18 |
Correct |
75 ms |
8508 KB |
n = 190000 |
19 |
Correct |
70 ms |
10896 KB |
n = 177777 |
20 |
Correct |
40 ms |
6676 KB |
n = 100000 |
21 |
Correct |
83 ms |
12216 KB |
n = 200000 |
22 |
Correct |
86 ms |
12096 KB |
n = 200000 |
23 |
Correct |
93 ms |
12104 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1108 KB |
n = 2 |
5 |
Correct |
1 ms |
1108 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |