oj.uz

Submission #986391

# Submission time Handle Problem Language Result Execution time Memory
986391 2024-05-20T12:42:18 Z Pyqe Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 121 ms 36908 KB 
#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long ma=1e9;
long long n,dsu[400069];
pair<long long,pair<long long,long long>> as[400069],ed[400069];
pair<long long,long long> pst[200069];

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

long long plan_roller_coaster(vector<int> ka,vector<int> la)
{
	long long i,k,l,w,c=0,z=0;
	
	n=ka.size()+1;
	for(i=1;i<=n;i++)
	{
		if(i<n)
		{
			k=ka[i-1];
			l=la[i-1];
		}
		else
		{
			k=ma+1;
			l=0;
		}
		z+=l-k;
		as[i*2-1]={k,{i,1}};
		as[i*2]={l,{i,-1}};
	}
	sort(as+1,as+n*2+1);
	for(i=1;i<=n*2;i++)
	{
		k=as[i].fr;
		l=as[i].sc.fr;
		w=as[i].sc.sc;
		z+=(k-as[i-1].fr)*abs(c);
		dsu[i]=i;
		if(c)
		{
			dsu[fd(i-1)]=fd(i);
		}
		c+=w;
		pst[l].fr=i;
		swap(pst[l].fr,pst[l].sc);
	}
	for(i=1;i<=n;i++)
	{
		k=pst[i].fr;
		l=pst[i].sc;
		dsu[fd(l)]=fd(k);
	}
	for(i=1;i<n*2;i++)
	{
		ed[i]={(as[i+1].fr-as[i].fr)*2,{fd(i),fd(i+1)}};
	}
	sort(ed+1,ed+n*2);
	for(i=1;i<n*2;i++)
	{
		w=ed[i].fr;
		k=ed[i].sc.fr;
		l=ed[i].sc.sc;
		z+=w*(fd(k)!=fd(l));
		dsu[fd(l)]=fd(k);
	}
	z/=2;
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB n = 2
2 Correct 1 ms 6492 KB n = 2
3 Correct 1 ms 6588 KB n = 2
4 Correct 1 ms 6492 KB n = 2
5 Correct 1 ms 6488 KB n = 2
6 Correct 1 ms 6492 KB n = 2
7 Correct 1 ms 6488 KB n = 3
8 Correct 1 ms 6492 KB n = 3
9 Correct 1 ms 6556 KB n = 3
10 Correct 1 ms 6492 KB n = 8
11 Correct 1 ms 6588 KB n = 8
12 Correct 1 ms 6492 KB n = 8
13 Correct 1 ms 6492 KB n = 8
14 Correct 1 ms 6492 KB n = 8
15 Correct 1 ms 6488 KB n = 8
16 Correct 1 ms 6588 KB n = 8
17 Correct 1 ms 6492 KB n = 8
18 Correct 1 ms 6492 KB n = 8
19 Correct 1 ms 6492 KB n = 3
20 Correct 1 ms 6592 KB n = 7
21 Correct 1 ms 6492 KB n = 8
22 Correct 2 ms 6492 KB n = 8
23 Correct 1 ms 6492 KB n = 8
24 Correct 1 ms 6492 KB n = 8
25 Correct 1 ms 6492 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB n = 2
2 Correct 1 ms 6492 KB n = 2
3 Correct 1 ms 6588 KB n = 2
4 Correct 1 ms 6492 KB n = 2
5 Correct 1 ms 6488 KB n = 2
6 Correct 1 ms 6492 KB n = 2
7 Correct 1 ms 6488 KB n = 3
8 Correct 1 ms 6492 KB n = 3
9 Correct 1 ms 6556 KB n = 3
10 Correct 1 ms 6492 KB n = 8
11 Correct 1 ms 6588 KB n = 8
12 Correct 1 ms 6492 KB n = 8
13 Correct 1 ms 6492 KB n = 8
14 Correct 1 ms 6492 KB n = 8
15 Correct 1 ms 6488 KB n = 8
16 Correct 1 ms 6588 KB n = 8
17 Correct 1 ms 6492 KB n = 8
18 Correct 1 ms 6492 KB n = 8
19 Correct 1 ms 6492 KB n = 3
20 Correct 1 ms 6592 KB n = 7
21 Correct 1 ms 6492 KB n = 8
22 Correct 2 ms 6492 KB n = 8
23 Correct 1 ms 6492 KB n = 8
24 Correct 1 ms 6492 KB n = 8
25 Correct 1 ms 6492 KB n = 8
26 Correct 1 ms 6492 KB n = 8
27 Correct 1 ms 6592 KB n = 8
28 Correct 1 ms 6492 KB n = 8
29 Correct 1 ms 6488 KB n = 16
30 Correct 1 ms 6488 KB n = 16
31 Correct 2 ms 6492 KB n = 16
32 Correct 1 ms 6492 KB n = 16
33 Correct 1 ms 6492 KB n = 16
34 Correct 2 ms 6488 KB n = 16
35 Correct 1 ms 6492 KB n = 16
36 Correct 1 ms 6492 KB n = 15
37 Correct 1 ms 6492 KB n = 8
38 Correct 1 ms 6752 KB n = 16
39 Correct 1 ms 6488 KB n = 16
40 Correct 1 ms 6488 KB n = 9
41 Correct 1 ms 6492 KB n = 16
42 Correct 2 ms 6492 KB n = 16
43 Correct 1 ms 6492 KB n = 16
44 Correct 1 ms 6492 KB n = 9
45 Correct 1 ms 6596 KB n = 15
46 Correct 1 ms 6492 KB n = 16
47 Correct 2 ms 6488 KB n = 16
48 Correct 1 ms 6492 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 34496 KB n = 199999
2 Correct 104 ms 35924 KB n = 199991
3 Correct 106 ms 35104 KB n = 199993
4 Correct 73 ms 30032 KB n = 152076
5 Correct 47 ms 23444 KB n = 93249
6 Correct 86 ms 31620 KB n = 199910
7 Correct 89 ms 31564 KB n = 199999
8 Correct 88 ms 31208 KB n = 199997
9 Correct 85 ms 32420 KB n = 171294
10 Correct 73 ms 30340 KB n = 140872
11 Correct 121 ms 31312 KB n = 199886
12 Correct 113 ms 31652 KB n = 199996
13 Correct 95 ms 31440 KB n = 200000
14 Correct 119 ms 31692 KB n = 199998
15 Correct 108 ms 31508 KB n = 200000
16 Correct 108 ms 31828 KB n = 199998
17 Correct 105 ms 35112 KB n = 200000
18 Correct 109 ms 31872 KB n = 190000
19 Correct 95 ms 33268 KB n = 177777
20 Correct 55 ms 22052 KB n = 100000
21 Correct 106 ms 32644 KB n = 200000
22 Correct 117 ms 32488 KB n = 200000
23 Correct 103 ms 32244 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB n = 2
2 Correct 1 ms 6492 KB n = 2
3 Correct 1 ms 6588 KB n = 2
4 Correct 1 ms 6492 KB n = 2
5 Correct 1 ms 6488 KB n = 2
6 Correct 1 ms 6492 KB n = 2
7 Correct 1 ms 6488 KB n = 3
8 Correct 1 ms 6492 KB n = 3
9 Correct 1 ms 6556 KB n = 3
10 Correct 1 ms 6492 KB n = 8
11 Correct 1 ms 6588 KB n = 8
12 Correct 1 ms 6492 KB n = 8
13 Correct 1 ms 6492 KB n = 8
14 Correct 1 ms 6492 KB n = 8
15 Correct 1 ms 6488 KB n = 8
16 Correct 1 ms 6588 KB n = 8
17 Correct 1 ms 6492 KB n = 8
18 Correct 1 ms 6492 KB n = 8
19 Correct 1 ms 6492 KB n = 3
20 Correct 1 ms 6592 KB n = 7
21 Correct 1 ms 6492 KB n = 8
22 Correct 2 ms 6492 KB n = 8
23 Correct 1 ms 6492 KB n = 8
24 Correct 1 ms 6492 KB n = 8
25 Correct 1 ms 6492 KB n = 8
26 Correct 1 ms 6492 KB n = 8
27 Correct 1 ms 6592 KB n = 8
28 Correct 1 ms 6492 KB n = 8
29 Correct 1 ms 6488 KB n = 16
30 Correct 1 ms 6488 KB n = 16
31 Correct 2 ms 6492 KB n = 16
32 Correct 1 ms 6492 KB n = 16
33 Correct 1 ms 6492 KB n = 16
34 Correct 2 ms 6488 KB n = 16
35 Correct 1 ms 6492 KB n = 16
36 Correct 1 ms 6492 KB n = 15
37 Correct 1 ms 6492 KB n = 8
38 Correct 1 ms 6752 KB n = 16
39 Correct 1 ms 6488 KB n = 16
40 Correct 1 ms 6488 KB n = 9
41 Correct 1 ms 6492 KB n = 16
42 Correct 2 ms 6492 KB n = 16
43 Correct 1 ms 6492 KB n = 16
44 Correct 1 ms 6492 KB n = 9
45 Correct 1 ms 6596 KB n = 15
46 Correct 1 ms 6492 KB n = 16
47 Correct 2 ms 6488 KB n = 16
48 Correct 1 ms 6492 KB n = 16
49 Correct 120 ms 34496 KB n = 199999
50 Correct 104 ms 35924 KB n = 199991
51 Correct 106 ms 35104 KB n = 199993
52 Correct 73 ms 30032 KB n = 152076
53 Correct 47 ms 23444 KB n = 93249
54 Correct 86 ms 31620 KB n = 199910
55 Correct 89 ms 31564 KB n = 199999
56 Correct 88 ms 31208 KB n = 199997
57 Correct 85 ms 32420 KB n = 171294
58 Correct 73 ms 30340 KB n = 140872
59 Correct 121 ms 31312 KB n = 199886
60 Correct 113 ms 31652 KB n = 199996
61 Correct 95 ms 31440 KB n = 200000
62 Correct 119 ms 31692 KB n = 199998
63 Correct 108 ms 31508 KB n = 200000
64 Correct 108 ms 31828 KB n = 199998
65 Correct 105 ms 35112 KB n = 200000
66 Correct 109 ms 31872 KB n = 190000
67 Correct 95 ms 33268 KB n = 177777
68 Correct 55 ms 22052 KB n = 100000
69 Correct 106 ms 32644 KB n = 200000
70 Correct 117 ms 32488 KB n = 200000
71 Correct 103 ms 32244 KB n = 200000
72 Correct 104 ms 35068 KB n = 200000
73 Correct 110 ms 35228 KB n = 200000
74 Correct 110 ms 36908 KB n = 200000
75 Correct 112 ms 35168 KB n = 200000
76 Correct 102 ms 35176 KB n = 200000
77 Correct 102 ms 36136 KB n = 200000
78 Correct 104 ms 32492 KB n = 200000
79 Correct 94 ms 33352 KB n = 184307
80 Correct 42 ms 20316 KB n = 76040
81 Correct 96 ms 31192 KB n = 199981
82 Correct 108 ms 31844 KB n = 199994
83 Correct 103 ms 31456 KB n = 199996
84 Correct 107 ms 31688 KB n = 199998
85 Correct 112 ms 31560 KB n = 200000
86 Correct 113 ms 32012 KB n = 199998
87 Correct 107 ms 35112 KB n = 200000
88 Correct 108 ms 32812 KB n = 200000
89 Correct 106 ms 35176 KB n = 200000
90 Correct 106 ms 32488 KB n = 200000
91 Correct 117 ms 32492 KB n = 200000
92 Correct 103 ms 32584 KB n = 200000