oj.uz

답안 #650017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650017 2022-10-11T23:17:53 Z jamezzz Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 168 ms 22820 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
#define maxn 200005
#define INF 1023456789
#define LINF 1023456789123456789

int par[maxn],rnk[maxn];
vector<pair<int,ii>> pts,edges;

int fp(int i){return par[i]==i?i:par[i]=fp(par[i]);}
bool join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return false;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
	return true;
}

ll plan_roller_coaster(vi s,vi t){
	int n=s.size();
	for(int i=0;i<n;++i){
		pts.pb({s[i],{1,i}});
		pts.pb({t[i],{-1,i}});
	}
	pts.pb({INF,{1,n}});
	pts.pb({1,{-1,n}});
	++n;
	for(int i=0;i<n;++i)par[i]=i;
	sort(all(pts));
	ll ans=0;
	int cur=0;
	for(int i=0;i<pts.size()-1;++i){
		cur+=pts[i].se.fi;
		ans+=(ll)max(cur,0)*(pts[i+1].fi-pts[i].fi);
		edges.pb({pts[i+1].fi-pts[i].fi,{pts[i].se.se,pts[i+1].se.se}});
		if(pts[i].fi==pts[i+1].fi||cur!=0)join(pts[i].se.se,pts[i+1].se.se);
	}
	sort(all(edges));
	for(int i=0;i<edges.size();++i){
		if(join(edges[i].se.fi,edges[i].se.se))ans+=edges[i].fi;
	}
	return ans;
}

Compilation message

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<pts.size()-1;++i){
      |              ~^~~~~~~~~~~~~
railroad.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<edges.size();++i){
      |              ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 1 ms 304 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 340 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 304 KB n = 8
11 Correct 1 ms 308 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 304 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 1 ms 304 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 304 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 1 ms 304 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 340 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 304 KB n = 8
11 Correct 1 ms 308 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 304 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 1 ms 304 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 304 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 304 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 1 ms 304 KB n = 16
35 Correct 1 ms 312 KB n = 16
36 Correct 1 ms 308 KB n = 15
37 Correct 1 ms 308 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 22000 KB n = 199999
2 Correct 147 ms 22132 KB n = 199991
3 Correct 152 ms 21972 KB n = 199993
4 Correct 123 ms 18772 KB n = 152076
5 Correct 66 ms 10740 KB n = 93249
6 Correct 144 ms 20820 KB n = 199910
7 Correct 149 ms 21284 KB n = 199999
8 Correct 157 ms 20904 KB n = 199997
9 Correct 126 ms 20024 KB n = 171294
10 Correct 108 ms 18320 KB n = 140872
11 Correct 147 ms 21400 KB n = 199886
12 Correct 156 ms 22192 KB n = 199996
13 Correct 152 ms 21680 KB n = 200000
14 Correct 149 ms 21916 KB n = 199998
15 Correct 146 ms 21852 KB n = 200000
16 Correct 142 ms 22332 KB n = 199998
17 Correct 138 ms 22004 KB n = 200000
18 Correct 151 ms 22108 KB n = 190000
19 Correct 133 ms 20592 KB n = 177777
20 Correct 69 ms 11160 KB n = 100000
21 Correct 150 ms 21932 KB n = 200000
22 Correct 149 ms 22700 KB n = 200000
23 Correct 150 ms 22768 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 1 ms 304 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 340 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 304 KB n = 8
11 Correct 1 ms 308 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 304 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 1 ms 304 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 304 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 304 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 1 ms 304 KB n = 16
35 Correct 1 ms 312 KB n = 16
36 Correct 1 ms 308 KB n = 15
37 Correct 1 ms 308 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 156 ms 22000 KB n = 199999
50 Correct 147 ms 22132 KB n = 199991
51 Correct 152 ms 21972 KB n = 199993
52 Correct 123 ms 18772 KB n = 152076
53 Correct 66 ms 10740 KB n = 93249
54 Correct 144 ms 20820 KB n = 199910
55 Correct 149 ms 21284 KB n = 199999
56 Correct 157 ms 20904 KB n = 199997
57 Correct 126 ms 20024 KB n = 171294
58 Correct 108 ms 18320 KB n = 140872
59 Correct 147 ms 21400 KB n = 199886
60 Correct 156 ms 22192 KB n = 199996
61 Correct 152 ms 21680 KB n = 200000
62 Correct 149 ms 21916 KB n = 199998
63 Correct 146 ms 21852 KB n = 200000
64 Correct 142 ms 22332 KB n = 199998
65 Correct 138 ms 22004 KB n = 200000
66 Correct 151 ms 22108 KB n = 190000
67 Correct 133 ms 20592 KB n = 177777
68 Correct 69 ms 11160 KB n = 100000
69 Correct 150 ms 21932 KB n = 200000
70 Correct 149 ms 22700 KB n = 200000
71 Correct 150 ms 22768 KB n = 200000
72 Correct 168 ms 22008 KB n = 200000
73 Correct 161 ms 22188 KB n = 200000
74 Correct 155 ms 21924 KB n = 200000
75 Correct 152 ms 21928 KB n = 200000
76 Correct 155 ms 21936 KB n = 200000
77 Correct 156 ms 22016 KB n = 200000
78 Correct 148 ms 22064 KB n = 200000
79 Correct 143 ms 20760 KB n = 184307
80 Correct 54 ms 9580 KB n = 76040
81 Correct 157 ms 21420 KB n = 199981
82 Correct 143 ms 22128 KB n = 199994
83 Correct 145 ms 21668 KB n = 199996
84 Correct 146 ms 21904 KB n = 199998
85 Correct 146 ms 21932 KB n = 200000
86 Correct 142 ms 22312 KB n = 199998
87 Correct 167 ms 21932 KB n = 200000
88 Correct 152 ms 22660 KB n = 200000
89 Correct 145 ms 21932 KB n = 200000
90 Correct 144 ms 22016 KB n = 200000
91 Correct 161 ms 22792 KB n = 200000
92 Correct 148 ms 22820 KB n = 200000