oj.uz

Submission #103076

# Submission time Handle Problem Language Result Execution time Memory
103076 2019-03-29T02:16:01 Z baluteshih Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 205 ms 33340 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	ll p,v,i;
	bool operator<(const mode&x)const{
		return p<x.p;
	}
};

struct edge
{
	ll a,b,w;
	bool operator<(const edge&x)const{
		return w<x.w;
	}
};

ll boss[200005];

ll finds(ll a)
{
	if(a==boss[a]) return a;
	return boss[a]=finds(boss[a]);
}

void Union(ll a,ll b)
{
	a=finds(a),b=finds(b);
	if(a==b) return;
	boss[a]=b;
}

ll plan_roller_coaster(vector<int> s,vector<int> t) 
{
    ll n=s.size()+1,ans=0,nw=0;
    vector<mode> v;
    vector<pii> interesting;
    vector<edge> e;
    s.pb(1000000001),t.pb(1);
    for(int i=0;i<n;++i)
    	boss[i]=i,v.pb(mode{s[i],1,i}),v.pb(mode{t[i],-1,i});
	sort(ALL(v));
	for(int i=0,t=0;i+1<v.size();)
	{
		interesting.pb(MP(v[i].p,v[i].i));
		while(t<v.size()&&v[i].p==v[t].p)
			nw+=v[t].v,++t;
		if(nw>0)
			ans+=nw*(v[t].p-v[i].p);
		if(nw!=0)
			Union(v[t].i,v[i].i);
		for(++i;i<t;++i)
			Union(v[i-1].i,v[i].i);
	}
	for(int i=0;i+1<interesting.size();++i)
		if(finds(interesting[i].S)!=finds(interesting[i+1].S))
			e.pb(edge{interesting[i].S,interesting[i+1].S,interesting[i+1].F-interesting[i].F});
	sort(ALL(e));
	for(auto i:e)
		if(finds(i.a)!=finds(i.b))
			Union(i.a,i.b),ans+=i.w;
	return ans;
}

Compilation message

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:55:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<n;++i)
     ^~~
railroad.cpp:57:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  sort(ALL(v));
  ^~~~
railroad.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,t=0;i+1<v.size();)
                  ~~~^~~~~~~~~
railroad.cpp:61:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(t<v.size()&&v[i].p==v[t].p)
         ~^~~~~~~~~
railroad.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<interesting.size();++i)
              ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 24024 KB n = 199999
2 Correct 165 ms 23904 KB n = 199991
3 Correct 172 ms 23976 KB n = 199993
4 Correct 133 ms 18884 KB n = 152076
5 Correct 76 ms 11644 KB n = 93249
6 Correct 163 ms 22428 KB n = 199910
7 Correct 161 ms 24760 KB n = 199999
8 Correct 157 ms 24092 KB n = 199997
9 Correct 145 ms 22296 KB n = 171294
10 Correct 125 ms 19356 KB n = 140872
11 Correct 146 ms 23864 KB n = 199886
12 Correct 153 ms 25068 KB n = 199996
13 Correct 153 ms 24376 KB n = 200000
14 Correct 167 ms 25316 KB n = 199998
15 Correct 180 ms 25220 KB n = 200000
16 Correct 205 ms 25532 KB n = 199998
17 Correct 154 ms 25668 KB n = 200000
18 Correct 154 ms 24584 KB n = 190000
19 Correct 174 ms 23280 KB n = 177777
20 Correct 86 ms 13016 KB n = 100000
21 Correct 175 ms 25696 KB n = 200000
22 Correct 187 ms 33340 KB n = 200000
23 Correct 169 ms 25528 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 256 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 384 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 256 KB n = 8
12 Correct 3 ms 256 KB n = 8
13 Correct 3 ms 384 KB n = 8
14 Correct 2 ms 256 KB n = 8
15 Correct 3 ms 256 KB n = 8
16 Correct 4 ms 256 KB n = 8
17 Correct 2 ms 256 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 3 ms 256 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 2 ms 256 KB n = 8
22 Correct 2 ms 384 KB n = 8
23 Correct 3 ms 384 KB n = 8
24 Correct 3 ms 384 KB n = 8
25 Correct 2 ms 256 KB n = 8
26 Correct 2 ms 256 KB n = 8
27 Correct 2 ms 256 KB n = 8
28 Correct 2 ms 256 KB n = 8
29 Correct 2 ms 256 KB n = 16
30 Correct 2 ms 256 KB n = 16
31 Correct 2 ms 256 KB n = 16
32 Correct 3 ms 256 KB n = 16
33 Correct 3 ms 256 KB n = 16
34 Correct 3 ms 408 KB n = 16
35 Correct 4 ms 384 KB n = 16
36 Correct 2 ms 256 KB n = 15
37 Correct 3 ms 384 KB n = 8
38 Correct 3 ms 256 KB n = 16
39 Correct 2 ms 372 KB n = 16
40 Correct 3 ms 256 KB n = 9
41 Correct 2 ms 384 KB n = 16
42 Correct 4 ms 512 KB n = 16
43 Correct 2 ms 256 KB n = 16
44 Correct 2 ms 256 KB n = 9
45 Correct 2 ms 256 KB n = 15
46 Correct 3 ms 384 KB n = 16
47 Correct 2 ms 384 KB n = 16
48 Correct 2 ms 256 KB n = 16
49 Correct 173 ms 24024 KB n = 199999
50 Correct 165 ms 23904 KB n = 199991
51 Correct 172 ms 23976 KB n = 199993
52 Correct 133 ms 18884 KB n = 152076
53 Correct 76 ms 11644 KB n = 93249
54 Correct 163 ms 22428 KB n = 199910
55 Correct 161 ms 24760 KB n = 199999
56 Correct 157 ms 24092 KB n = 199997
57 Correct 145 ms 22296 KB n = 171294
58 Correct 125 ms 19356 KB n = 140872
59 Correct 146 ms 23864 KB n = 199886
60 Correct 153 ms 25068 KB n = 199996
61 Correct 153 ms 24376 KB n = 200000
62 Correct 167 ms 25316 KB n = 199998
63 Correct 180 ms 25220 KB n = 200000
64 Correct 205 ms 25532 KB n = 199998
65 Correct 154 ms 25668 KB n = 200000
66 Correct 154 ms 24584 KB n = 190000
67 Correct 174 ms 23280 KB n = 177777
68 Correct 86 ms 13016 KB n = 100000
69 Correct 175 ms 25696 KB n = 200000
70 Correct 187 ms 33340 KB n = 200000
71 Correct 169 ms 25528 KB n = 200000
72 Correct 160 ms 25508 KB n = 200000
73 Correct 188 ms 25660 KB n = 200000
74 Correct 174 ms 25532 KB n = 200000
75 Correct 171 ms 25708 KB n = 200000
76 Correct 192 ms 25536 KB n = 200000
77 Correct 188 ms 21948 KB n = 200000
78 Correct 169 ms 31328 KB n = 200000
79 Correct 143 ms 23808 KB n = 184307
80 Correct 65 ms 10452 KB n = 76040
81 Correct 130 ms 23968 KB n = 199981
82 Correct 155 ms 25020 KB n = 199994
83 Correct 190 ms 24372 KB n = 199996
84 Correct 181 ms 25152 KB n = 199998
85 Correct 162 ms 25052 KB n = 200000
86 Correct 158 ms 25404 KB n = 199998
87 Correct 177 ms 25600 KB n = 200000
88 Correct 174 ms 25664 KB n = 200000
89 Correct 157 ms 25536 KB n = 200000
90 Correct 158 ms 25540 KB n = 200000
91 Correct 203 ms 33316 KB n = 200000
92 Correct 181 ms 25632 KB n = 200000