oj.uz

답안 #310728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310728 2020-10-07T18:00:57 Z rqi Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 617 ms 40244 KB 
#include "railroad.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
 
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second

struct DSU{
	vi e;
	void init(int n){
		e = vi(n, -1);
	}
	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}
	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};
 
ll plan_roller_coaster(vi s, vi t) {
	s.pb(1000000000);
	t.pb(0);
	int n = sz(s);

	vpi v;
	for(int i = 0; i < n; i++){
		v.pb(mp(s[i], -1));
		v.pb(mp(t[i], 1));
	}
	sort(all(v));
	map<int, int> rv;

	for(int i = 0; i < 2*n; i++){
		//cout << i << " " << v[i].f << "\n";
		rv[v[i].f] = i;
	}

	DSU dsu;
	dsu.init(2*n);

	for(int i = 0; i < n; i++){
		dsu.unite(rv[s[i]], rv[t[i]]);
	}

	ll ans = 0;
	for(int i = 0; i < 2*n; i++){
		if(i-1 >= 0) v[i].s+=v[i-1].s;
		if(i+1 < 2*n){
			if(v[i].s < 0){
				dsu.unite(i, i+1);
				ans+=ll(v[i+1].f-v[i].f)*ll(-v[i].s);
				//cout << "<: " << i << " " << i+1 << "\n";
			}
			else if(v[i].s > 0){
				dsu.unite(i, i+1);
				//cout << ">: " << i << " " << i+1 << "\n";
			}
		}
	}

	vector<pair<int, pi>> eds;

	for(int i = 0; i+1 < 2*n; i++){
		eds.pb(mp(v[i+1].f-v[i].f, mp(i, i+1)));
	}

	sort(all(eds));

	for(auto u: eds){
		if(dsu.unite(u.s.f, u.s.s)){
			ans+=u.f;
		}
	}
	
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 36304 KB n = 199999
2 Correct 595 ms 36176 KB n = 199991
3 Correct 602 ms 36304 KB n = 199993
4 Correct 424 ms 29896 KB n = 152076
5 Correct 230 ms 17428 KB n = 93249
6 Correct 509 ms 32976 KB n = 199910
7 Correct 511 ms 35920 KB n = 199999
8 Correct 489 ms 33104 KB n = 199997
9 Correct 512 ms 32436 KB n = 171294
10 Correct 395 ms 28448 KB n = 140872
11 Correct 535 ms 33104 KB n = 199886
12 Correct 515 ms 35972 KB n = 199996
13 Correct 495 ms 33744 KB n = 200000
14 Correct 482 ms 36048 KB n = 199998
15 Correct 484 ms 35504 KB n = 200000
16 Correct 509 ms 36080 KB n = 199998
17 Correct 597 ms 36176 KB n = 200000
18 Correct 581 ms 34976 KB n = 190000
19 Correct 525 ms 33264 KB n = 177777
20 Correct 231 ms 18300 KB n = 100000
21 Correct 548 ms 36304 KB n = 200000
22 Correct 560 ms 36176 KB n = 200000
23 Correct 611 ms 36176 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 2
2 Correct 0 ms 256 KB n = 2
3 Correct 0 ms 256 KB n = 2
4 Correct 0 ms 256 KB n = 2
5 Correct 0 ms 256 KB n = 2
6 Correct 1 ms 256 KB n = 2
7 Correct 1 ms 256 KB n = 3
8 Correct 1 ms 256 KB n = 3
9 Correct 0 ms 256 KB n = 3
10 Correct 1 ms 256 KB n = 8
11 Correct 0 ms 256 KB n = 8
12 Correct 0 ms 256 KB n = 8
13 Correct 0 ms 256 KB n = 8
14 Correct 1 ms 384 KB n = 8
15 Correct 0 ms 256 KB n = 8
16 Correct 0 ms 256 KB n = 8
17 Correct 1 ms 256 KB n = 8
18 Correct 0 ms 256 KB n = 8
19 Correct 1 ms 288 KB n = 3
20 Correct 0 ms 256 KB n = 7
21 Correct 0 ms 256 KB n = 8
22 Correct 1 ms 256 KB n = 8
23 Correct 0 ms 256 KB n = 8
24 Correct 0 ms 256 KB n = 8
25 Correct 1 ms 256 KB n = 8
26 Correct 1 ms 288 KB n = 8
27 Correct 0 ms 256 KB n = 8
28 Correct 0 ms 256 KB n = 8
29 Correct 0 ms 256 KB n = 16
30 Correct 1 ms 256 KB n = 16
31 Correct 0 ms 256 KB n = 16
32 Correct 0 ms 256 KB n = 16
33 Correct 0 ms 256 KB n = 16
34 Correct 1 ms 256 KB n = 16
35 Correct 0 ms 256 KB n = 16
36 Correct 0 ms 256 KB n = 15
37 Correct 0 ms 256 KB n = 8
38 Correct 0 ms 256 KB n = 16
39 Correct 1 ms 256 KB n = 16
40 Correct 0 ms 256 KB n = 9
41 Correct 1 ms 256 KB n = 16
42 Correct 0 ms 256 KB n = 16
43 Correct 1 ms 256 KB n = 16
44 Correct 0 ms 256 KB n = 9
45 Correct 0 ms 256 KB n = 15
46 Correct 0 ms 256 KB n = 16
47 Correct 0 ms 256 KB n = 16
48 Correct 1 ms 256 KB n = 16
49 Correct 616 ms 36304 KB n = 199999
50 Correct 595 ms 36176 KB n = 199991
51 Correct 602 ms 36304 KB n = 199993
52 Correct 424 ms 29896 KB n = 152076
53 Correct 230 ms 17428 KB n = 93249
54 Correct 509 ms 32976 KB n = 199910
55 Correct 511 ms 35920 KB n = 199999
56 Correct 489 ms 33104 KB n = 199997
57 Correct 512 ms 32436 KB n = 171294
58 Correct 395 ms 28448 KB n = 140872
59 Correct 535 ms 33104 KB n = 199886
60 Correct 515 ms 35972 KB n = 199996
61 Correct 495 ms 33744 KB n = 200000
62 Correct 482 ms 36048 KB n = 199998
63 Correct 484 ms 35504 KB n = 200000
64 Correct 509 ms 36080 KB n = 199998
65 Correct 597 ms 36176 KB n = 200000
66 Correct 581 ms 34976 KB n = 190000
67 Correct 525 ms 33264 KB n = 177777
68 Correct 231 ms 18300 KB n = 100000
69 Correct 548 ms 36304 KB n = 200000
70 Correct 560 ms 36176 KB n = 200000
71 Correct 611 ms 36176 KB n = 200000
72 Correct 616 ms 36212 KB n = 200000
73 Correct 609 ms 36176 KB n = 200000
74 Correct 606 ms 36176 KB n = 200000
75 Correct 617 ms 40244 KB n = 200000
76 Correct 607 ms 40144 KB n = 200000
77 Correct 393 ms 30672 KB n = 200000
78 Correct 387 ms 30772 KB n = 200000
79 Correct 567 ms 37456 KB n = 184307
80 Correct 177 ms 16536 KB n = 76040
81 Correct 534 ms 35920 KB n = 199981
82 Correct 520 ms 39248 KB n = 199994
83 Correct 486 ms 36596 KB n = 199996
84 Correct 480 ms 39124 KB n = 199998
85 Correct 474 ms 38480 KB n = 200000
86 Correct 499 ms 39632 KB n = 199998
87 Correct 615 ms 40144 KB n = 200000
88 Correct 600 ms 40144 KB n = 200000
89 Correct 597 ms 40232 KB n = 200000
90 Correct 547 ms 40144 KB n = 200000
91 Correct 573 ms 40144 KB n = 200000
92 Correct 596 ms 40148 KB n = 200000