oj.uz

답안 #292530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292530 2020-09-07T08:44:08 Z shayan_p Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 705 ms 35556 KB 
// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "railroad.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
int pr[maxn];
 
int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return 0;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
    return 1;
}
 

ll plan_roller_coaster(vector<int> a, vector<int> b){
    memset(pr, -1, sizeof pr);
    
    int n = sz(a);
    map<int, int> mp;
    mp[0]++; // first of all
    for(int x : a)
	mp[x]--;
    for(int x : b)
	mp[x]++;
 
    vector<int> tot;
    for(int x : a)
	tot.PB(x);
    for(int x : b)
	tot.PB(x);
    tot.PB(0);
    sort(tot.begin(), tot.end());
    tot.resize( unique(tot.begin(), tot.end()) - tot.begin() );
    
    auto comp = [&](int x){
		    return lower_bound(tot.begin(), tot.end(), x) - tot.begin();
		};
    int mrgs = 0;
    for(int i = 0; i < n; i++){
	mrgs+= mrg(comp(a[i]), comp(b[i]));
    }

    ll ans = 0;
    int sum = 0, ID = 0;
    for(auto it = mp.begin(); it != mp.end(); it++, ID++){
	sum+= it->S;
	if(sum < 0)
	    ans+= 1ll * abs(sum) * (tot[ID+1] - tot[ID]);
	if(sum != 0)
	    mrgs+= mrg(ID, ID + 1);
    }
    vector< pair<int, pii> > eds;
    for(int i = 0; i < sz(tot)-1; i++){
	eds.PB({tot[i+1] - tot[i], {i, i+1}});
    }
    sort(eds.begin(), eds.end());
    for(auto it : eds){
	if(mrg(it.S.F, it.S.S))
	    ans+= it.F;
    }    
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 685 ms 35296 KB n = 199999
2 Correct 684 ms 35428 KB n = 199991
3 Correct 667 ms 35552 KB n = 199993
4 Correct 466 ms 29672 KB n = 152076
5 Correct 250 ms 18152 KB n = 93249
6 Correct 586 ms 31204 KB n = 199910
7 Correct 673 ms 34276 KB n = 199999
8 Correct 603 ms 31332 KB n = 199997
9 Correct 568 ms 31208 KB n = 171294
10 Correct 420 ms 27620 KB n = 140872
11 Correct 592 ms 31460 KB n = 199886
12 Correct 654 ms 34408 KB n = 199996
13 Correct 586 ms 31996 KB n = 200000
14 Correct 624 ms 34260 KB n = 199998
15 Correct 615 ms 34024 KB n = 200000
16 Correct 659 ms 34436 KB n = 199998
17 Correct 537 ms 34532 KB n = 200000
18 Correct 624 ms 33476 KB n = 190000
19 Correct 477 ms 32100 KB n = 177777
20 Correct 262 ms 19048 KB n = 100000
21 Correct 652 ms 34660 KB n = 200000
22 Correct 642 ms 34788 KB n = 200000
23 Correct 662 ms 34524 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1920 KB n = 2
2 Correct 1 ms 1920 KB n = 2
3 Correct 2 ms 1920 KB n = 2
4 Correct 2 ms 1920 KB n = 2
5 Correct 2 ms 2048 KB n = 2
6 Correct 1 ms 1920 KB n = 2
7 Correct 2 ms 1920 KB n = 3
8 Correct 1 ms 1920 KB n = 3
9 Correct 1 ms 1920 KB n = 3
10 Correct 1 ms 1920 KB n = 8
11 Correct 1 ms 1920 KB n = 8
12 Correct 1 ms 1920 KB n = 8
13 Correct 1 ms 1920 KB n = 8
14 Correct 1 ms 1920 KB n = 8
15 Correct 2 ms 1920 KB n = 8
16 Correct 1 ms 1920 KB n = 8
17 Correct 1 ms 1920 KB n = 8
18 Correct 2 ms 1824 KB n = 8
19 Correct 1 ms 1920 KB n = 3
20 Correct 1 ms 1920 KB n = 7
21 Correct 1 ms 1920 KB n = 8
22 Correct 1 ms 1920 KB n = 8
23 Correct 1 ms 1920 KB n = 8
24 Correct 1 ms 1920 KB n = 8
25 Correct 1 ms 1920 KB n = 8
26 Correct 1 ms 1920 KB n = 8
27 Correct 2 ms 1920 KB n = 8
28 Correct 1 ms 1920 KB n = 8
29 Correct 1 ms 1920 KB n = 16
30 Correct 1 ms 1920 KB n = 16
31 Correct 2 ms 1920 KB n = 16
32 Correct 1 ms 1920 KB n = 16
33 Correct 2 ms 1920 KB n = 16
34 Correct 2 ms 1920 KB n = 16
35 Correct 1 ms 1920 KB n = 16
36 Correct 1 ms 1920 KB n = 15
37 Correct 1 ms 1920 KB n = 8
38 Correct 1 ms 1920 KB n = 16
39 Correct 2 ms 1920 KB n = 16
40 Correct 1 ms 1920 KB n = 9
41 Correct 1 ms 1920 KB n = 16
42 Correct 1 ms 1824 KB n = 16
43 Correct 1 ms 1920 KB n = 16
44 Correct 2 ms 1920 KB n = 9
45 Correct 2 ms 1920 KB n = 15
46 Correct 1 ms 1920 KB n = 16
47 Correct 1 ms 1920 KB n = 16
48 Correct 1 ms 1920 KB n = 16
49 Correct 685 ms 35296 KB n = 199999
50 Correct 684 ms 35428 KB n = 199991
51 Correct 667 ms 35552 KB n = 199993
52 Correct 466 ms 29672 KB n = 152076
53 Correct 250 ms 18152 KB n = 93249
54 Correct 586 ms 31204 KB n = 199910
55 Correct 673 ms 34276 KB n = 199999
56 Correct 603 ms 31332 KB n = 199997
57 Correct 568 ms 31208 KB n = 171294
58 Correct 420 ms 27620 KB n = 140872
59 Correct 592 ms 31460 KB n = 199886
60 Correct 654 ms 34408 KB n = 199996
61 Correct 586 ms 31996 KB n = 200000
62 Correct 624 ms 34260 KB n = 199998
63 Correct 615 ms 34024 KB n = 200000
64 Correct 659 ms 34436 KB n = 199998
65 Correct 537 ms 34532 KB n = 200000
66 Correct 624 ms 33476 KB n = 190000
67 Correct 477 ms 32100 KB n = 177777
68 Correct 262 ms 19048 KB n = 100000
69 Correct 652 ms 34660 KB n = 200000
70 Correct 642 ms 34788 KB n = 200000
71 Correct 662 ms 34524 KB n = 200000
72 Correct 705 ms 34532 KB n = 200000
73 Correct 672 ms 34532 KB n = 200000
74 Correct 654 ms 35172 KB n = 200000
75 Correct 551 ms 35172 KB n = 200000
76 Correct 578 ms 35296 KB n = 200000
77 Correct 447 ms 22888 KB n = 200000
78 Correct 453 ms 22760 KB n = 200000
79 Correct 606 ms 33512 KB n = 184307
80 Correct 192 ms 16236 KB n = 76040
81 Correct 593 ms 32020 KB n = 199981
82 Correct 654 ms 35176 KB n = 199994
83 Correct 605 ms 32616 KB n = 199996
84 Correct 629 ms 34788 KB n = 199998
85 Correct 628 ms 34664 KB n = 200000
86 Correct 654 ms 35220 KB n = 199998
87 Correct 567 ms 35300 KB n = 200000
88 Correct 678 ms 35300 KB n = 200000
89 Correct 573 ms 35556 KB n = 200000
90 Correct 653 ms 35172 KB n = 200000
91 Correct 627 ms 35300 KB n = 200000
92 Correct 631 ms 35172 KB n = 200000