oj.uz

답안 #600615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600615 2022-07-21T06:18:47 Z wiwiho Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 189 ms 35520 KB 
#include "railroad.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

vector<int> dsu;

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}

void unionDSU(int a, int b){
    a = findDSU(a); b = findDSU(b);
    dsu[b] = a;
}

struct info{
    int x, id, ty;
};

struct seg{
    int id, l, r;
};

long long plan_roller_coaster(vector<int> S, vector<int> T){
    int n = (int) S.size();

    vector<info> v;
    for(int i = 0; i < n; i++){
        //cerr << "test " << i << " : " << S[i] << " " << T[i] << "\n";
        v.eb(info({S[i], i, 1}));
        v.eb(info({T[i], i, 0}));
    }
    v.eb(info({0, n, 0}));
    v.eb(info({1000000001, n, 1}));

    sort(iter(v), [&](info x, info y){ return mp(x.x, x.ty) < mp(y.x, y.ty); });
    vector<info> nv;
    int ts = n + 1;

    ll ans = 0;

    deque<info> lone;
    int cnt = 0;
    for(info& i : v){
        int x = i.x, id = i.id, ty = i.ty;
        if(ty == 1){
            if(cnt) cnt--;
            else lone.eb(i);
            continue;
        }
        if(lone.empty()){
            cnt++;
            continue;
        }
        nv.eb(info({lone.front().x, ts++, 0}));
        nv.eb(info({x, ts++, 1}));
        ans += x - lone.front().x;
        i.x = lone.front().x;
        lone.pof;
    }

    for(info i : nv) v.eb(i);
    sort(iter(v), [&](info x, info y){ return mp(x.x, x.ty) < mp(y.x, y.ty); });

    dsu.resize(v.size());
    iota(iter(dsu), 0);
    

    vector<int> left;
    vector<seg> b;
    
    for(info i : v){
        int x = i.x, id = i.id, ty = i.ty;
        if(ty == 0){
            left.eb(id);
            b.eb(seg({id, x, -1}));
            continue;
        }
        int l = left.back();
        left.pob;
        unionDSU(l, id);
        while(b.back().id != l){
            unionDSU(b.back().id, id);
            b.pob;
        }
        b.back().r = x;
    }

    vector<pair<int, pii>> e;
    for(int i = 0; i + 1 < (int)b.size(); i++){
        if(findDSU(b[i].id) == findDSU(b[i + 1].id)) continue;
        e.eb(mp(b[i + 1].l - b[i].r, mp(b[i].id, b[i + 1].id)));
    }
    lsort(e);
    for(auto i : e){
        int w = i.F, u = i.S.F, v = i.S.S;
        if(findDSU(u) == findDSU(v)) continue;
        ans += w;
        unionDSU(u, v);
    }
    
    return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:106:22: warning: unused variable 'id' [-Wunused-variable]
  106 |         int x = i.x, id = i.id, ty = i.ty;
      |                      ^~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 12620 KB n = 199999
2 Correct 189 ms 19932 KB n = 199991
3 Correct 185 ms 27212 KB n = 199993
4 Correct 84 ms 9776 KB n = 152076
5 Correct 53 ms 5884 KB n = 93249
6 Correct 108 ms 9664 KB n = 199910
7 Correct 107 ms 10316 KB n = 199999
8 Correct 108 ms 10284 KB n = 199997
9 Correct 102 ms 9284 KB n = 171294
10 Correct 81 ms 9296 KB n = 140872
11 Correct 102 ms 9652 KB n = 199886
12 Correct 106 ms 10448 KB n = 199996
13 Correct 105 ms 10540 KB n = 200000
14 Correct 125 ms 18248 KB n = 199998
15 Correct 136 ms 19512 KB n = 200000
16 Correct 144 ms 20528 KB n = 199998
17 Correct 145 ms 32380 KB n = 200000
18 Correct 143 ms 20580 KB n = 190000
19 Correct 88 ms 14088 KB n = 177777
20 Correct 54 ms 5068 KB n = 100000
21 Correct 111 ms 9772 KB n = 200000
22 Correct 138 ms 17456 KB n = 200000
23 Correct 107 ms 15012 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 0 ms 212 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 1 ms 300 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 0 ms 300 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 1 ms 300 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 0 ms 296 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 0 ms 300 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 123 ms 12620 KB n = 199999
50 Correct 189 ms 19932 KB n = 199991
51 Correct 185 ms 27212 KB n = 199993
52 Correct 84 ms 9776 KB n = 152076
53 Correct 53 ms 5884 KB n = 93249
54 Correct 108 ms 9664 KB n = 199910
55 Correct 107 ms 10316 KB n = 199999
56 Correct 108 ms 10284 KB n = 199997
57 Correct 102 ms 9284 KB n = 171294
58 Correct 81 ms 9296 KB n = 140872
59 Correct 102 ms 9652 KB n = 199886
60 Correct 106 ms 10448 KB n = 199996
61 Correct 105 ms 10540 KB n = 200000
62 Correct 125 ms 18248 KB n = 199998
63 Correct 136 ms 19512 KB n = 200000
64 Correct 144 ms 20528 KB n = 199998
65 Correct 145 ms 32380 KB n = 200000
66 Correct 143 ms 20580 KB n = 190000
67 Correct 88 ms 14088 KB n = 177777
68 Correct 54 ms 5068 KB n = 100000
69 Correct 111 ms 9772 KB n = 200000
70 Correct 138 ms 17456 KB n = 200000
71 Correct 107 ms 15012 KB n = 200000
72 Correct 125 ms 15792 KB n = 200000
73 Correct 157 ms 17288 KB n = 200000
74 Correct 180 ms 30300 KB n = 200000
75 Correct 154 ms 35520 KB n = 200000
76 Correct 97 ms 18596 KB n = 200000
77 Correct 105 ms 18124 KB n = 200000
78 Correct 129 ms 20472 KB n = 200000
79 Correct 113 ms 12764 KB n = 184307
80 Correct 46 ms 6104 KB n = 76040
81 Correct 107 ms 12452 KB n = 199981
82 Correct 111 ms 13588 KB n = 199994
83 Correct 106 ms 13336 KB n = 199996
84 Correct 131 ms 21280 KB n = 199998
85 Correct 140 ms 22308 KB n = 200000
86 Correct 144 ms 23624 KB n = 199998
87 Correct 146 ms 35508 KB n = 200000
88 Correct 157 ms 24524 KB n = 200000
89 Correct 108 ms 18484 KB n = 200000
90 Correct 119 ms 12864 KB n = 200000
91 Correct 147 ms 20580 KB n = 200000
92 Correct 111 ms 18228 KB n = 200000