oj.uz

Submission #59170

# Submission time Handle Problem Language Result Execution time Memory
59170 2018-07-20T21:59:43 Z TadijaSebez Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 216 ms 161924 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int inf=1e9+7;
struct Event
{
	int x,t,id;
	Event(int a, int b, int c){ x=a,t=b,id=c;}
	bool operator < (Event b) const { return x<b.x || (x==b.x && t<b.t);}
};
struct Edge
{
	int u,v,w;
	Edge(int a, int b, int c){ u=a,v=b,w=c;}
	bool operator < (Edge b) const { return w<b.w;}
};
const int N=200050;
int p[N];
void init(){ for(int i=0;i<N;i++) p[i]=i;}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
int max(int a, int b){ return a>b?a:b;}
ll plan_roller_coaster(vector<int> s, vector<int> t)
{
	int n=s.size(),i;
	vector<Event> events;
	for(i=0;i<n;i++) events.pb(Event(s[i],1,i+1)),events.pb(Event(t[i],-1,i+1));
	events.pb(Event(inf,1,n+1));
	events.pb(Event(1,-1,n+1));
	int balance=0;
	ll sol=0;
	init();
	sort(events.begin(),events.end());
	vector<Edge> edges;
	for(i=0;i<events.size()-1;i++)
	{
		int len=events[i+1].x-events[i].x;
		balance+=events[i].t;
		//printf("%i %i %i %i %i\n",events[i].x,len,balance,events[i].id,events[i+1].id);
		sol+=(ll)max(0,balance)*len;
		if(balance==0 && len>0) edges.pb(Edge(events[i].id,events[i+1].id,len));
		else Union(events[i].id,events[i+1].id);
	}
	sort(edges.begin(),edges.end());
	for(i=0;i<edges.size();i++)
	{
		//printf("%i %i %i %i %i\n",edges[i].u,edges[i].v,edges[i].w,Find(edges[i].u),Find(edges[i].v));
		if(Find(edges[i].u)!=Find(edges[i].v))
		{
			sol+=edges[i].w;
			Union(edges[i].u,edges[i].v);
		}
	}
	return sol;
}
/*int main()
{
	int n,i;
	vector<int> s,t;
	scanf("%i",&n);
	s.resize(n);t.resize(n);
	for(i=0;i<n;i++) scanf("%i %i",&s[i],&t[i]);
	printf("%lld\n",plan_roller_coaster(s,t));
	return 0;
}*/

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<events.size()-1;i++)
          ~^~~~~~~~~~~~~~~~
railroad.cpp:49:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<edges.size();i++)
          ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB n = 2
2 Correct 4 ms 1144 KB n = 2
3 Correct 3 ms 1216 KB n = 2
4 Correct 3 ms 1268 KB n = 2
5 Correct 3 ms 1268 KB n = 2
6 Correct 3 ms 1268 KB n = 2
7 Correct 3 ms 1336 KB n = 3
8 Correct 3 ms 1336 KB n = 3
9 Correct 3 ms 1336 KB n = 3
10 Correct 3 ms 1352 KB n = 8
11 Correct 3 ms 1352 KB n = 8
12 Correct 3 ms 1388 KB n = 8
13 Correct 5 ms 1460 KB n = 8
14 Correct 4 ms 1460 KB n = 8
15 Correct 3 ms 1460 KB n = 8
16 Correct 3 ms 1460 KB n = 8
17 Correct 3 ms 1480 KB n = 8
18 Correct 2 ms 1480 KB n = 8
19 Correct 3 ms 1480 KB n = 3
20 Correct 3 ms 1516 KB n = 7
21 Correct 3 ms 1516 KB n = 8
22 Correct 3 ms 1516 KB n = 8
23 Correct 3 ms 1516 KB n = 8
24 Correct 3 ms 1516 KB n = 8
25 Correct 3 ms 1516 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB n = 2
2 Correct 4 ms 1144 KB n = 2
3 Correct 3 ms 1216 KB n = 2
4 Correct 3 ms 1268 KB n = 2
5 Correct 3 ms 1268 KB n = 2
6 Correct 3 ms 1268 KB n = 2
7 Correct 3 ms 1336 KB n = 3
8 Correct 3 ms 1336 KB n = 3
9 Correct 3 ms 1336 KB n = 3
10 Correct 3 ms 1352 KB n = 8
11 Correct 3 ms 1352 KB n = 8
12 Correct 3 ms 1388 KB n = 8
13 Correct 5 ms 1460 KB n = 8
14 Correct 4 ms 1460 KB n = 8
15 Correct 3 ms 1460 KB n = 8
16 Correct 3 ms 1460 KB n = 8
17 Correct 3 ms 1480 KB n = 8
18 Correct 2 ms 1480 KB n = 8
19 Correct 3 ms 1480 KB n = 3
20 Correct 3 ms 1516 KB n = 7
21 Correct 3 ms 1516 KB n = 8
22 Correct 3 ms 1516 KB n = 8
23 Correct 3 ms 1516 KB n = 8
24 Correct 3 ms 1516 KB n = 8
25 Correct 3 ms 1516 KB n = 8
26 Correct 3 ms 1516 KB n = 8
27 Correct 3 ms 1516 KB n = 8
28 Correct 3 ms 1516 KB n = 8
29 Correct 3 ms 1516 KB n = 16
30 Correct 4 ms 1516 KB n = 16
31 Correct 3 ms 1516 KB n = 16
32 Correct 3 ms 1516 KB n = 16
33 Correct 3 ms 1700 KB n = 16
34 Correct 3 ms 1700 KB n = 16
35 Correct 3 ms 1700 KB n = 16
36 Correct 4 ms 1700 KB n = 15
37 Correct 3 ms 1700 KB n = 8
38 Correct 3 ms 1700 KB n = 16
39 Correct 3 ms 1700 KB n = 16
40 Correct 3 ms 1700 KB n = 9
41 Correct 4 ms 1700 KB n = 16
42 Correct 3 ms 1700 KB n = 16
43 Correct 2 ms 1700 KB n = 16
44 Correct 3 ms 1700 KB n = 9
45 Correct 3 ms 1700 KB n = 15
46 Correct 3 ms 1700 KB n = 16
47 Correct 4 ms 1700 KB n = 16
48 Correct 2 ms 1700 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 14096 KB n = 199999
2 Correct 159 ms 17976 KB n = 199991
3 Correct 167 ms 21876 KB n = 199993
4 Correct 129 ms 23788 KB n = 152076
5 Correct 100 ms 23788 KB n = 93249
6 Correct 123 ms 29100 KB n = 199910
7 Correct 138 ms 32212 KB n = 199999
8 Correct 143 ms 34988 KB n = 199997
9 Correct 129 ms 37624 KB n = 171294
10 Correct 105 ms 39896 KB n = 140872
11 Correct 131 ms 43628 KB n = 199886
12 Correct 143 ms 47412 KB n = 199996
13 Correct 176 ms 50248 KB n = 200000
14 Correct 171 ms 58524 KB n = 199998
15 Correct 180 ms 61032 KB n = 200000
16 Correct 154 ms 64312 KB n = 199998
17 Correct 151 ms 65484 KB n = 200000
18 Correct 153 ms 66700 KB n = 190000
19 Correct 122 ms 71420 KB n = 177777
20 Correct 74 ms 71420 KB n = 100000
21 Correct 165 ms 76048 KB n = 200000
22 Correct 216 ms 84524 KB n = 200000
23 Correct 176 ms 88376 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB n = 2
2 Correct 4 ms 1144 KB n = 2
3 Correct 3 ms 1216 KB n = 2
4 Correct 3 ms 1268 KB n = 2
5 Correct 3 ms 1268 KB n = 2
6 Correct 3 ms 1268 KB n = 2
7 Correct 3 ms 1336 KB n = 3
8 Correct 3 ms 1336 KB n = 3
9 Correct 3 ms 1336 KB n = 3
10 Correct 3 ms 1352 KB n = 8
11 Correct 3 ms 1352 KB n = 8
12 Correct 3 ms 1388 KB n = 8
13 Correct 5 ms 1460 KB n = 8
14 Correct 4 ms 1460 KB n = 8
15 Correct 3 ms 1460 KB n = 8
16 Correct 3 ms 1460 KB n = 8
17 Correct 3 ms 1480 KB n = 8
18 Correct 2 ms 1480 KB n = 8
19 Correct 3 ms 1480 KB n = 3
20 Correct 3 ms 1516 KB n = 7
21 Correct 3 ms 1516 KB n = 8
22 Correct 3 ms 1516 KB n = 8
23 Correct 3 ms 1516 KB n = 8
24 Correct 3 ms 1516 KB n = 8
25 Correct 3 ms 1516 KB n = 8
26 Correct 3 ms 1516 KB n = 8
27 Correct 3 ms 1516 KB n = 8
28 Correct 3 ms 1516 KB n = 8
29 Correct 3 ms 1516 KB n = 16
30 Correct 4 ms 1516 KB n = 16
31 Correct 3 ms 1516 KB n = 16
32 Correct 3 ms 1516 KB n = 16
33 Correct 3 ms 1700 KB n = 16
34 Correct 3 ms 1700 KB n = 16
35 Correct 3 ms 1700 KB n = 16
36 Correct 4 ms 1700 KB n = 15
37 Correct 3 ms 1700 KB n = 8
38 Correct 3 ms 1700 KB n = 16
39 Correct 3 ms 1700 KB n = 16
40 Correct 3 ms 1700 KB n = 9
41 Correct 4 ms 1700 KB n = 16
42 Correct 3 ms 1700 KB n = 16
43 Correct 2 ms 1700 KB n = 16
44 Correct 3 ms 1700 KB n = 9
45 Correct 3 ms 1700 KB n = 15
46 Correct 3 ms 1700 KB n = 16
47 Correct 4 ms 1700 KB n = 16
48 Correct 2 ms 1700 KB n = 16
49 Correct 177 ms 14096 KB n = 199999
50 Correct 159 ms 17976 KB n = 199991
51 Correct 167 ms 21876 KB n = 199993
52 Correct 129 ms 23788 KB n = 152076
53 Correct 100 ms 23788 KB n = 93249
54 Correct 123 ms 29100 KB n = 199910
55 Correct 138 ms 32212 KB n = 199999
56 Correct 143 ms 34988 KB n = 199997
57 Correct 129 ms 37624 KB n = 171294
58 Correct 105 ms 39896 KB n = 140872
59 Correct 131 ms 43628 KB n = 199886
60 Correct 143 ms 47412 KB n = 199996
61 Correct 176 ms 50248 KB n = 200000
62 Correct 171 ms 58524 KB n = 199998
63 Correct 180 ms 61032 KB n = 200000
64 Correct 154 ms 64312 KB n = 199998
65 Correct 151 ms 65484 KB n = 200000
66 Correct 153 ms 66700 KB n = 190000
67 Correct 122 ms 71420 KB n = 177777
68 Correct 74 ms 71420 KB n = 100000
69 Correct 165 ms 76048 KB n = 200000
70 Correct 216 ms 84524 KB n = 200000
71 Correct 176 ms 88376 KB n = 200000
72 Correct 172 ms 88376 KB n = 200000
73 Correct 179 ms 91532 KB n = 200000
74 Correct 205 ms 95416 KB n = 200000
75 Correct 204 ms 99188 KB n = 200000
76 Correct 161 ms 103220 KB n = 200000
77 Correct 147 ms 109480 KB n = 200000
78 Correct 160 ms 115500 KB n = 200000
79 Correct 155 ms 115500 KB n = 184307
80 Correct 62 ms 115500 KB n = 76040
81 Correct 145 ms 118516 KB n = 199981
82 Correct 174 ms 122272 KB n = 199994
83 Correct 143 ms 125124 KB n = 199996
84 Correct 163 ms 133348 KB n = 199998
85 Correct 182 ms 135920 KB n = 200000
86 Correct 183 ms 139052 KB n = 199998
87 Correct 142 ms 140404 KB n = 200000
88 Correct 207 ms 141852 KB n = 200000
89 Correct 150 ms 148164 KB n = 200000
90 Correct 150 ms 149608 KB n = 200000
91 Correct 173 ms 158064 KB n = 200000
92 Correct 188 ms 161924 KB n = 200000