oj.uz

답안 #255575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255575 2020-08-01T10:05:14 Z Mercenary Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 218 ms 15080 KB 
//#include "railroad.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 4e5 + 5;

int lab[maxn];
int sum[maxn];

vector<int> val;
int n;
int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
bool Merge(int u , int v){
    u = FindLab(u);v = FindLab(v);
    if(u == v)return 0;
    if(lab[u] > lab[v])swap(u , v);
    lab[u] += lab[v];
    lab[v] = u;
    return 1;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
    memset(lab,-1,sizeof lab);
    ll res = 0;
    n = s.size();
    for(int i = 0 ; i < n ; ++i){
        val.pb(s[i]);val.pb(t[i]);
    }
    sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
    for(int i = 0 ; i < n ; ++i){
        s[i] = lower_bound(val.begin(),val.end(),s[i]) - val.begin();
        t[i] = lower_bound(val.begin(),val.end(),t[i]) - val.begin();
        Merge(s[i] , t[i]);
        sum[s[i]]++;sum[t[i]]--;
    }
    int cur = 1;
    vector<pair<int,int>> edges;
    for(int i = (int)val.size() - 1 ; i > 0 ; --i){
        cur += sum[i];
        if(cur < 0){
            res -= 1ll * cur * (val[i] - val[i - 1]);
            Merge(i,i-1);
        }else if(cur > 0)Merge(i,i-1);
        else if(cur == 0)edges.pb(mp(val[i] - val[i - 1] , i));
    }
    sort(edges.begin(),edges.end());
    for(auto & c : edges){
        if(Merge(c.second,c.second-1))res += c.first;
    }
    return res;
}


//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    if(fopen(taskname".INP","r")){
//		freopen(taskname".INP", "r",stdin);
//		freopen(taskname".OUT", "w",stdout);
//    }
//
//}

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 1 ms 1920 KB n = 2
4 Correct 1 ms 1920 KB n = 2
5 Correct 1 ms 1920 KB n = 2
6 Correct 1 ms 1920 KB n = 2
7 Correct 1 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 2048 KB n = 8
13 Correct 1 ms 1920 KB n = 8
14 Correct 1 ms 1920 KB n = 8
15 Correct 1 ms 1920 KB n = 8
16 Correct 1 ms 1920 KB n = 8
17 Correct 1 ms 1920 KB n = 8
18 Correct 1 ms 1920 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 1 ms 1920 KB n = 2
4 Correct 1 ms 1920 KB n = 2
5 Correct 1 ms 1920 KB n = 2
6 Correct 1 ms 1920 KB n = 2
7 Correct 1 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 2048 KB n = 8
13 Correct 1 ms 1920 KB n = 8
14 Correct 1 ms 1920 KB n = 8
15 Correct 1 ms 1920 KB n = 8
16 Correct 1 ms 1920 KB n = 8
17 Correct 1 ms 1920 KB n = 8
18 Correct 1 ms 1920 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 1 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 1 ms 1920 KB n = 16
32 Correct 1 ms 1920 KB n = 16
33 Correct 1 ms 1920 KB n = 16
34 Correct 1 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 1 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 1920 KB n = 16
43 Correct 1 ms 1920 KB n = 16
44 Correct 1 ms 1920 KB n = 9
45 Correct 1 ms 1920 KB n = 15
46 Correct 2 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 184 ms 12136 KB n = 199999
2 Correct 200 ms 12232 KB n = 199991
3 Correct 189 ms 12136 KB n = 199993
4 Correct 137 ms 9448 KB n = 152076
5 Correct 82 ms 6764 KB n = 93249
6 Correct 172 ms 10728 KB n = 199910
7 Correct 168 ms 11368 KB n = 199999
8 Correct 160 ms 10728 KB n = 199997
9 Correct 161 ms 10600 KB n = 171294
10 Correct 131 ms 9192 KB n = 140872
11 Correct 163 ms 10856 KB n = 199886
12 Correct 188 ms 11752 KB n = 199996
13 Correct 178 ms 11240 KB n = 200000
14 Correct 185 ms 14440 KB n = 199998
15 Correct 196 ms 14184 KB n = 200000
16 Correct 195 ms 14696 KB n = 199998
17 Correct 188 ms 12264 KB n = 200000
18 Correct 175 ms 11624 KB n = 190000
19 Correct 163 ms 11112 KB n = 177777
20 Correct 88 ms 7148 KB n = 100000
21 Correct 184 ms 12136 KB n = 200000
22 Correct 214 ms 15080 KB n = 200000
23 Correct 218 ms 15080 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 1 ms 1920 KB n = 2
4 Correct 1 ms 1920 KB n = 2
5 Correct 1 ms 1920 KB n = 2
6 Correct 1 ms 1920 KB n = 2
7 Correct 1 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 2048 KB n = 8
13 Correct 1 ms 1920 KB n = 8
14 Correct 1 ms 1920 KB n = 8
15 Correct 1 ms 1920 KB n = 8
16 Correct 1 ms 1920 KB n = 8
17 Correct 1 ms 1920 KB n = 8
18 Correct 1 ms 1920 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 1 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 1 ms 1920 KB n = 16
32 Correct 1 ms 1920 KB n = 16
33 Correct 1 ms 1920 KB n = 16
34 Correct 1 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 1 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 1920 KB n = 16
43 Correct 1 ms 1920 KB n = 16
44 Correct 1 ms 1920 KB n = 9
45 Correct 1 ms 1920 KB n = 15
46 Correct 2 ms 1920 KB n = 16
47 Correct 1 ms 1920 KB n = 16
48 Correct 1 ms 1920 KB n = 16
49 Correct 184 ms 12136 KB n = 199999
50 Correct 200 ms 12232 KB n = 199991
51 Correct 189 ms 12136 KB n = 199993
52 Correct 137 ms 9448 KB n = 152076
53 Correct 82 ms 6764 KB n = 93249
54 Correct 172 ms 10728 KB n = 199910
55 Correct 168 ms 11368 KB n = 199999
56 Correct 160 ms 10728 KB n = 199997
57 Correct 161 ms 10600 KB n = 171294
58 Correct 131 ms 9192 KB n = 140872
59 Correct 163 ms 10856 KB n = 199886
60 Correct 188 ms 11752 KB n = 199996
61 Correct 178 ms 11240 KB n = 200000
62 Correct 185 ms 14440 KB n = 199998
63 Correct 196 ms 14184 KB n = 200000
64 Correct 195 ms 14696 KB n = 199998
65 Correct 188 ms 12264 KB n = 200000
66 Correct 175 ms 11624 KB n = 190000
67 Correct 163 ms 11112 KB n = 177777
68 Correct 88 ms 7148 KB n = 100000
69 Correct 184 ms 12136 KB n = 200000
70 Correct 214 ms 15080 KB n = 200000
71 Correct 218 ms 15080 KB n = 200000
72 Correct 183 ms 12264 KB n = 200000
73 Correct 187 ms 12136 KB n = 200000
74 Correct 187 ms 12392 KB n = 200000
75 Correct 183 ms 12264 KB n = 200000
76 Correct 177 ms 12208 KB n = 200000
77 Correct 172 ms 11496 KB n = 200000
78 Correct 191 ms 14312 KB n = 200000
79 Correct 177 ms 11240 KB n = 184307
80 Correct 66 ms 5868 KB n = 76040
81 Correct 164 ms 11000 KB n = 199981
82 Correct 172 ms 11880 KB n = 199994
83 Correct 164 ms 11240 KB n = 199996
84 Correct 199 ms 14364 KB n = 199998
85 Correct 196 ms 14312 KB n = 200000
86 Correct 198 ms 14568 KB n = 199998
87 Correct 181 ms 12264 KB n = 200000
88 Correct 189 ms 12136 KB n = 200000
89 Correct 176 ms 12136 KB n = 200000
90 Correct 181 ms 12136 KB n = 200000
91 Correct 214 ms 15080 KB n = 200000
92 Correct 218 ms 15080 KB n = 200000