oj.uz

답안 #170717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170717 2019-12-26T07:56:08 Z dennisstar Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 404 ms 48232 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int par[400010], deg[400010], chk[400010];
int get(int i) {
	if (par[i]==i) return i;
	else return par[i]=get(par[i]);
}
vim V[400010], cp;
int N, M, tp;
ll ans;

void dfs(int now, int num) {
	chk[now]=num;
	for (int i:V[now]) if (!chk[i]) dfs(i, num);
}

ll plan_roller_coaster(vim s, vim t) {
	N=s.size();

	//coordinate compression
	for (int i:s) cp.push_back(i);
	for (int i:t) cp.push_back(i);
	sort(all(cp)); cp.erase(unique(all(cp)), cp.end()); M=cp.size();
	vim S, T;
	S.push_back(0); T.push_back(0);
	for (int i:s) {
		int lb=lower_bound(all(cp), i)-cp.begin();
		S.push_back(lb+1);
		deg[lb+1]++;
	}
	for (int i:t) {
		int lb=lower_bound(all(cp), i)-cp.begin();
		T.push_back(lb+1);
		deg[lb+1]--;
	}

	//generate edges
	for (int i=1; i<=N; i++) V[S[i]].push_back(T[i]);
	for (int i=1; i<M; i++) {
		int req=(i==1?1:0);
		int now=req-deg[i];
		if (now>0) {
			deg[i]+=now;
			deg[i+1]-=now;
			V[i].push_back(i+1);
		}
		else if (now<0) { 
			deg[i]+=now;
			deg[i+1]-=now;
			V[i+1].push_back(i);
			ans+=(ll)abs(now)*(cp[i]-cp[i-1]);
		}
	}

	//mst
	for (int i=1; i<M; i++) if (!chk[i]) dfs(i, ++tp);
	for (int i=1; i<=tp; i++) par[i]=i;
	vector<pii> e;
	for (int i=1; i<M; i++) if (chk[i]!=chk[i+1]) e.push_back({cp[i]-cp[i-1], i});
	sort(all(e));
	for (pii pi:e) {
		int x1=get(chk[pi.se]), x2=get(chk[pi.se+1]);
		if (x1!=x2) {
			ans+=(ll)pi.fi;
			par[x2]=x1;
		}
	}

	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 319 ms 48068 KB n = 199999
2 Correct 359 ms 40908 KB n = 199991
3 Correct 335 ms 47640 KB n = 199993
4 Correct 302 ms 32872 KB n = 152076
5 Correct 144 ms 24300 KB n = 93249
6 Correct 340 ms 34920 KB n = 199910
7 Correct 327 ms 40588 KB n = 199999
8 Correct 359 ms 36840 KB n = 199997
9 Correct 357 ms 36332 KB n = 171294
10 Correct 261 ms 31516 KB n = 140872
11 Correct 363 ms 35276 KB n = 199886
12 Correct 382 ms 40516 KB n = 199996
13 Correct 312 ms 37776 KB n = 200000
14 Correct 314 ms 44008 KB n = 199998
15 Correct 311 ms 41832 KB n = 200000
16 Correct 325 ms 42600 KB n = 199998
17 Correct 296 ms 41828 KB n = 200000
18 Correct 331 ms 40808 KB n = 190000
19 Correct 289 ms 43880 KB n = 177777
20 Correct 155 ms 25324 KB n = 100000
21 Correct 404 ms 41144 KB n = 200000
22 Correct 352 ms 39144 KB n = 200000
23 Correct 361 ms 48104 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9848 KB n = 2
2 Correct 11 ms 9720 KB n = 2
3 Correct 10 ms 9720 KB n = 2
4 Correct 10 ms 9720 KB n = 2
5 Correct 10 ms 9720 KB n = 2
6 Correct 10 ms 9720 KB n = 2
7 Correct 10 ms 9720 KB n = 3
8 Correct 10 ms 9720 KB n = 3
9 Correct 10 ms 9720 KB n = 3
10 Correct 10 ms 9720 KB n = 8
11 Correct 10 ms 9720 KB n = 8
12 Correct 13 ms 9720 KB n = 8
13 Correct 13 ms 9720 KB n = 8
14 Correct 10 ms 9720 KB n = 8
15 Correct 15 ms 9720 KB n = 8
16 Correct 12 ms 9720 KB n = 8
17 Correct 22 ms 9848 KB n = 8
18 Correct 10 ms 9720 KB n = 8
19 Correct 12 ms 9720 KB n = 3
20 Correct 10 ms 9720 KB n = 7
21 Correct 12 ms 9720 KB n = 8
22 Correct 10 ms 9740 KB n = 8
23 Correct 10 ms 9720 KB n = 8
24 Correct 10 ms 9724 KB n = 8
25 Correct 10 ms 9720 KB n = 8
26 Correct 10 ms 9720 KB n = 8
27 Correct 10 ms 9720 KB n = 8
28 Correct 10 ms 9720 KB n = 8
29 Correct 10 ms 9720 KB n = 16
30 Correct 10 ms 9720 KB n = 16
31 Correct 10 ms 9720 KB n = 16
32 Correct 10 ms 9720 KB n = 16
33 Correct 10 ms 9724 KB n = 16
34 Correct 10 ms 9720 KB n = 16
35 Correct 10 ms 9720 KB n = 16
36 Correct 10 ms 9720 KB n = 15
37 Correct 10 ms 9720 KB n = 8
38 Correct 10 ms 9720 KB n = 16
39 Correct 12 ms 9720 KB n = 16
40 Correct 10 ms 9692 KB n = 9
41 Correct 10 ms 9800 KB n = 16
42 Correct 10 ms 9724 KB n = 16
43 Correct 10 ms 9692 KB n = 16
44 Correct 10 ms 9720 KB n = 9
45 Correct 10 ms 9720 KB n = 15
46 Correct 10 ms 9720 KB n = 16
47 Correct 10 ms 9720 KB n = 16
48 Correct 10 ms 9656 KB n = 16
49 Correct 319 ms 48068 KB n = 199999
50 Correct 359 ms 40908 KB n = 199991
51 Correct 335 ms 47640 KB n = 199993
52 Correct 302 ms 32872 KB n = 152076
53 Correct 144 ms 24300 KB n = 93249
54 Correct 340 ms 34920 KB n = 199910
55 Correct 327 ms 40588 KB n = 199999
56 Correct 359 ms 36840 KB n = 199997
57 Correct 357 ms 36332 KB n = 171294
58 Correct 261 ms 31516 KB n = 140872
59 Correct 363 ms 35276 KB n = 199886
60 Correct 382 ms 40516 KB n = 199996
61 Correct 312 ms 37776 KB n = 200000
62 Correct 314 ms 44008 KB n = 199998
63 Correct 311 ms 41832 KB n = 200000
64 Correct 325 ms 42600 KB n = 199998
65 Correct 296 ms 41828 KB n = 200000
66 Correct 331 ms 40808 KB n = 190000
67 Correct 289 ms 43880 KB n = 177777
68 Correct 155 ms 25324 KB n = 100000
69 Correct 404 ms 41144 KB n = 200000
70 Correct 352 ms 39144 KB n = 200000
71 Correct 361 ms 48104 KB n = 200000
72 Correct 328 ms 48068 KB n = 200000
73 Correct 351 ms 40936 KB n = 200000
74 Correct 312 ms 46416 KB n = 200000
75 Correct 297 ms 48148 KB n = 200000
76 Correct 300 ms 48204 KB n = 200000
77 Correct 279 ms 34068 KB n = 200000
78 Correct 289 ms 31592 KB n = 200000
79 Correct 330 ms 37020 KB n = 184307
80 Correct 130 ms 21680 KB n = 76040
81 Correct 297 ms 35052 KB n = 199981
82 Correct 317 ms 40424 KB n = 199994
83 Correct 308 ms 37668 KB n = 199996
84 Correct 330 ms 44008 KB n = 199998
85 Correct 372 ms 42060 KB n = 200000
86 Correct 315 ms 42472 KB n = 199998
87 Correct 280 ms 41996 KB n = 200000
88 Correct 328 ms 42212 KB n = 200000
89 Correct 290 ms 48104 KB n = 200000
90 Correct 349 ms 41012 KB n = 200000
91 Correct 346 ms 39156 KB n = 200000
92 Correct 354 ms 48232 KB n = 200000