oj.uz

Submission #764480

# Submission time Handle Problem Language Result Execution time Memory
764480 2023-06-23T12:45:27 Z marvinthang Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 158 ms 15080 KB 
/*************************************
*    author: marvinthang             *
*    created: 23.06.2023 19:16:39    *
*************************************/

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

struct DisjointSet {
    
    int n, *lab = nullptr;

    DisjointSet(int _n = 0) {
        resize(_n);
    }

    void reset(void) {
        memset(lab, -1, (n + 1) * sizeof(int));
    }

    void resize(int _n) {
         if (lab != nullptr) delete[] lab;
         n = _n;
         lab = new int[n + 1];
         reset();
    }

    int find(int u) {
        assert(u <= n);
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool connected(int u, int v) { return find(u) == find(v); }
    bool isRoot(int u) { return lab[u] < 0; }
    int size(int u) { return -lab[find(u)]; }

    bool join(int u, int v) {
        if ((u = find(u)) == (v = find(v))) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

};

using DSU = DisjointSet;

// end of template

long long plan_roller_coaster(vector <int> s, vector <int> t) {
    int n = (int) s.size();
    vector <int> v(s);
    v.insert(v.end(), ALL(t));
    sort(ALL(v));
    v.erase(unique(ALL(v)), v.end());
    int m = v.size();
    vector <int> pref(m);
    pref[0] = -1;
    DSU dsu(m);
    REP(i, n) {
        s[i] = lower_bound(ALL(v), s[i]) - v.begin();
        t[i] = lower_bound(ALL(v), t[i]) - v.begin();
        ++pref[s[i]];
        --pref[t[i]];
        dsu.join(s[i], t[i]);
    }
    long long res = 0;
    vector <pair <int, int>> edges;
    REP(i, m - 1) {
        pref[i + 1] += pref[i];
        if (pref[i] > 0) res += 1LL * pref[i] * (v[i + 1] - v[i]);
        if (pref[i]) dsu.join(i, i + 1);
        else edges.emplace_back(v[i + 1] - v[i], i);
    }
    sort(ALL(edges));
    for (auto [w, u]: edges) if (dsu.join(u, u + 1)) res += w;
    return res;
}

#ifdef LOCAL
#include "railroad.h"
#include <cstdio>
#include <cassert>

int main() {
    file("railroad");
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 300 KB n = 2
5 Correct 1 ms 304 KB n = 2
6 Correct 1 ms 300 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 296 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 296 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 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 300 KB n = 2
5 Correct 1 ms 304 KB n = 2
6 Correct 1 ms 300 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 296 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 296 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 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 296 KB n = 8
29 Correct 1 ms 228 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 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 300 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 0 ms 212 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 12004 KB n = 199999
2 Correct 121 ms 11928 KB n = 199991
3 Correct 120 ms 11952 KB n = 199993
4 Correct 86 ms 8812 KB n = 152076
5 Correct 52 ms 5724 KB n = 93249
6 Correct 112 ms 10280 KB n = 199910
7 Correct 110 ms 11180 KB n = 199999
8 Correct 108 ms 10328 KB n = 199997
9 Correct 101 ms 10176 KB n = 171294
10 Correct 80 ms 8520 KB n = 140872
11 Correct 111 ms 10392 KB n = 199886
12 Correct 111 ms 11692 KB n = 199996
13 Correct 113 ms 10928 KB n = 200000
14 Correct 137 ms 14212 KB n = 199998
15 Correct 123 ms 14012 KB n = 200000
16 Correct 134 ms 14484 KB n = 199998
17 Correct 112 ms 11964 KB n = 200000
18 Correct 112 ms 11428 KB n = 190000
19 Correct 98 ms 10712 KB n = 177777
20 Correct 55 ms 6092 KB n = 100000
21 Correct 137 ms 12008 KB n = 200000
22 Correct 136 ms 15080 KB n = 200000
23 Correct 158 ms 15036 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 300 KB n = 2
5 Correct 1 ms 304 KB n = 2
6 Correct 1 ms 300 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 296 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 296 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 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 296 KB n = 8
29 Correct 1 ms 228 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 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 300 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 0 ms 212 KB n = 16
49 Correct 122 ms 12004 KB n = 199999
50 Correct 121 ms 11928 KB n = 199991
51 Correct 120 ms 11952 KB n = 199993
52 Correct 86 ms 8812 KB n = 152076
53 Correct 52 ms 5724 KB n = 93249
54 Correct 112 ms 10280 KB n = 199910
55 Correct 110 ms 11180 KB n = 199999
56 Correct 108 ms 10328 KB n = 199997
57 Correct 101 ms 10176 KB n = 171294
58 Correct 80 ms 8520 KB n = 140872
59 Correct 111 ms 10392 KB n = 199886
60 Correct 111 ms 11692 KB n = 199996
61 Correct 113 ms 10928 KB n = 200000
62 Correct 137 ms 14212 KB n = 199998
63 Correct 123 ms 14012 KB n = 200000
64 Correct 134 ms 14484 KB n = 199998
65 Correct 112 ms 11964 KB n = 200000
66 Correct 112 ms 11428 KB n = 190000
67 Correct 98 ms 10712 KB n = 177777
68 Correct 55 ms 6092 KB n = 100000
69 Correct 137 ms 12008 KB n = 200000
70 Correct 136 ms 15080 KB n = 200000
71 Correct 158 ms 15036 KB n = 200000
72 Correct 115 ms 11944 KB n = 200000
73 Correct 133 ms 12080 KB n = 200000
74 Correct 122 ms 12004 KB n = 200000
75 Correct 115 ms 11948 KB n = 200000
76 Correct 113 ms 12004 KB n = 200000
77 Correct 101 ms 10420 KB n = 200000
78 Correct 122 ms 13520 KB n = 200000
79 Correct 107 ms 10860 KB n = 184307
80 Correct 41 ms 4748 KB n = 76040
81 Correct 112 ms 10300 KB n = 199981
82 Correct 112 ms 11708 KB n = 199994
83 Correct 113 ms 10916 KB n = 199996
84 Correct 123 ms 14124 KB n = 199998
85 Correct 127 ms 14124 KB n = 200000
86 Correct 128 ms 14600 KB n = 199998
87 Correct 111 ms 11936 KB n = 200000
88 Correct 116 ms 11952 KB n = 200000
89 Correct 135 ms 11948 KB n = 200000
90 Correct 113 ms 11948 KB n = 200000
91 Correct 142 ms 15016 KB n = 200000
92 Correct 143 ms 15020 KB n = 200000