oj.uz

답안 #388630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388630 2021-04-12T10:26:26 Z alishahali1382 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 279 ms 24580 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const int inf=1000000010;
const ll INF=10000001000000000ll;
const int MAXN=400010;

int n, m, k;
int S[MAXN], T[MAXN], ps[MAXN];
int par[MAXN];
bool mark[MAXN];
// ll dp[1<<16][16];
vector<int> comp;
ll ans;

int getpar(int x){ return (par[x]==x?x:par[x]=getpar(par[x]));}

ll plan_roller_coaster(vector<int> s, vector<int> t){
	n=s.size();/*
	if (n<=16){
		for (int mask=1; mask<(1<<n); mask++){
			int v=__builtin_ctz(mask);
			if (mask==(1<<v)) dp[mask][v]=0;
			else{
				for (int v=0; v<n; v++) if (mask&(1<<v)){
					dp[mask][v]=INF;
					for (int u=0; u<n; u++) if (u!=v && mask&(1<<u))
						dp[mask][v]=min(dp[mask][v], dp[mask^(1<<v)][u] + max(0, t[u]-s[v]));
				}
			}
		}
		ll ans=INF;
		for (int i=0; i<n; i++) ans=min(ans, dp[(1<<n)-1][i]);
		return ans;
	}*/
	for (int i=1; i<=n; i++) S[i]=s[i-1], T[i]=t[i-1];
	S[0]=inf;
	T[0]=1;
	for (int i=0; i<=n; i++){
		comp.pb(T[i]);
		comp.pb(S[i]);
	}
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	m=comp.size();
	iota(par, par+m, 0);
	for (int i=0; i<=n; i++){
		S[i]=lower_bound(all(comp), S[i])-comp.begin();
		T[i]=lower_bound(all(comp), T[i])-comp.begin();
		par[getpar(S[i])]=getpar(T[i]);
		// debug2(S[i], T[i])
		ps[S[i]]++;
		ps[T[i]]--;
	}
	for (int i=1; i<m; i++) ps[i]+=ps[i-1];
	for (int i=0; i+1<m; i++) if (ps[i]){
		// debug2(i, comp[i])
		par[getpar(i)]=getpar(i+1);
		if (ps[i]>0) ans+=1ll*ps[i]*(comp[i+1]-comp[i]);
	}
	// debug(ans)
	vector<pair<ll, pii>> E;
	for (int i=0; i<=n; i++) mark[getpar(S[i])]=1;
	int last=-1;
	for (int i=0; i<m; i++) if (mark[getpar(i)]){
		if (last!=-1) E.pb({comp[i]-comp[last], {i, last}});
		last=i;
	}
	sort(all(E));
	for (auto p:E){
		int x=getpar(p.second.first), y=getpar(p.second.second);
		if (x!=y){
			par[x]=y;
			ans+=p.first;
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 18028 KB n = 199999
2 Correct 279 ms 18024 KB n = 199991
3 Correct 265 ms 18100 KB n = 199993
4 Correct 191 ms 15816 KB n = 152076
5 Correct 114 ms 8888 KB n = 93249
6 Correct 242 ms 17588 KB n = 199910
7 Correct 239 ms 18868 KB n = 199999
8 Correct 216 ms 18380 KB n = 199997
9 Correct 228 ms 16736 KB n = 171294
10 Correct 199 ms 15260 KB n = 140872
11 Correct 223 ms 17876 KB n = 199886
12 Correct 247 ms 19504 KB n = 199996
13 Correct 233 ms 19128 KB n = 200000
14 Correct 245 ms 21940 KB n = 199998
15 Correct 245 ms 20784 KB n = 200000
16 Correct 254 ms 20548 KB n = 199998
17 Correct 249 ms 24372 KB n = 200000
18 Correct 242 ms 18028 KB n = 190000
19 Correct 209 ms 22496 KB n = 177777
20 Correct 118 ms 9260 KB n = 100000
21 Correct 251 ms 17972 KB n = 200000
22 Correct 242 ms 18360 KB n = 200000
23 Correct 252 ms 18116 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB n = 2
2 Correct 1 ms 252 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 0 ms 332 KB n = 2
5 Correct 1 ms 332 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 1 ms 332 KB n = 3
8 Correct 1 ms 204 KB n = 3
9 Correct 0 ms 332 KB n = 3
10 Correct 0 ms 204 KB n = 8
11 Correct 0 ms 332 KB n = 8
12 Correct 0 ms 332 KB n = 8
13 Correct 0 ms 204 KB n = 8
14 Correct 0 ms 332 KB n = 8
15 Correct 0 ms 332 KB n = 8
16 Correct 0 ms 204 KB n = 8
17 Correct 0 ms 332 KB n = 8
18 Correct 1 ms 204 KB n = 8
19 Correct 0 ms 332 KB n = 3
20 Correct 0 ms 204 KB n = 7
21 Correct 0 ms 204 KB n = 8
22 Correct 1 ms 332 KB n = 8
23 Correct 0 ms 332 KB n = 8
24 Correct 1 ms 204 KB n = 8
25 Correct 1 ms 332 KB n = 8
26 Correct 1 ms 204 KB n = 8
27 Correct 1 ms 204 KB n = 8
28 Correct 0 ms 332 KB n = 8
29 Correct 0 ms 332 KB n = 16
30 Correct 1 ms 332 KB n = 16
31 Correct 0 ms 332 KB n = 16
32 Correct 0 ms 332 KB n = 16
33 Correct 1 ms 332 KB n = 16
34 Correct 0 ms 332 KB n = 16
35 Correct 1 ms 332 KB n = 16
36 Correct 0 ms 332 KB n = 15
37 Correct 1 ms 204 KB n = 8
38 Correct 0 ms 332 KB n = 16
39 Correct 1 ms 332 KB n = 16
40 Correct 0 ms 204 KB n = 9
41 Correct 0 ms 332 KB n = 16
42 Correct 0 ms 332 KB n = 16
43 Correct 1 ms 332 KB n = 16
44 Correct 0 ms 204 KB n = 9
45 Correct 0 ms 204 KB n = 15
46 Correct 0 ms 332 KB n = 16
47 Correct 0 ms 204 KB n = 16
48 Correct 1 ms 332 KB n = 16
49 Correct 261 ms 18028 KB n = 199999
50 Correct 279 ms 18024 KB n = 199991
51 Correct 265 ms 18100 KB n = 199993
52 Correct 191 ms 15816 KB n = 152076
53 Correct 114 ms 8888 KB n = 93249
54 Correct 242 ms 17588 KB n = 199910
55 Correct 239 ms 18868 KB n = 199999
56 Correct 216 ms 18380 KB n = 199997
57 Correct 228 ms 16736 KB n = 171294
58 Correct 199 ms 15260 KB n = 140872
59 Correct 223 ms 17876 KB n = 199886
60 Correct 247 ms 19504 KB n = 199996
61 Correct 233 ms 19128 KB n = 200000
62 Correct 245 ms 21940 KB n = 199998
63 Correct 245 ms 20784 KB n = 200000
64 Correct 254 ms 20548 KB n = 199998
65 Correct 249 ms 24372 KB n = 200000
66 Correct 242 ms 18028 KB n = 190000
67 Correct 209 ms 22496 KB n = 177777
68 Correct 118 ms 9260 KB n = 100000
69 Correct 251 ms 17972 KB n = 200000
70 Correct 242 ms 18360 KB n = 200000
71 Correct 252 ms 18116 KB n = 200000
72 Correct 261 ms 17992 KB n = 200000
73 Correct 276 ms 17972 KB n = 200000
74 Correct 266 ms 18356 KB n = 200000
75 Correct 257 ms 18276 KB n = 200000
76 Correct 240 ms 18324 KB n = 200000
77 Correct 190 ms 19004 KB n = 200000
78 Correct 184 ms 12764 KB n = 200000
79 Correct 252 ms 17612 KB n = 184307
80 Correct 111 ms 8428 KB n = 76040
81 Correct 227 ms 17896 KB n = 199981
82 Correct 244 ms 19808 KB n = 199994
83 Correct 228 ms 19480 KB n = 199996
84 Correct 241 ms 22288 KB n = 199998
85 Correct 236 ms 21044 KB n = 200000
86 Correct 258 ms 20872 KB n = 199998
87 Correct 271 ms 24544 KB n = 200000
88 Correct 250 ms 19668 KB n = 200000
89 Correct 245 ms 24580 KB n = 200000
90 Correct 254 ms 18356 KB n = 200000
91 Correct 247 ms 18700 KB n = 200000
92 Correct 270 ms 18268 KB n = 200000