oj.uz

Submission #332102

# Submission time Handle Problem Language Result Execution time Memory
332102 2020-12-01T12:52:57 Z LifeHappen__ Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 268 ms 24532 KB 
#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back

struct dsu {
  vector <int> par;
  void init(int n){
    par.assign(n, 0);
    for (int i = 0; i < n; ++i) par[i] = i;
  }
  int findset(int u) {
    if(par[u] == u) return u;
    return par[u] = findset(par[u]);
  }
  bool mergeset(int u, int v) {
    u = findset(u), v = findset(v);
    if(u == v) return false;
    par[v] = u; return true;
  }
} pa;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
  int n = s.size();
  #define int long long
  vector<int> vals;
  for (auto &v : s) vals.pb(v);
  for (auto &v : t) vals.pb(v);
  sort(begin(vals), end(vals));
  vals.resize(unique(begin(vals), end(vals)) - begin(vals));
  vector<int> can(vals.size() + 5, 0);
  pa.init(vals.size() + 10);
  for (int i = 0; i < n; ++i) {
    s[i] = lower_bound(begin(vals), end(vals), s[i]) - begin(vals);
    t[i] = lower_bound(begin(vals), end(vals), t[i]) - begin(vals);
    can[s[i]]++;
    can[t[i]]--;
    pa.mergeset(s[i], t[i]);
  }
  int m = vals.size();
  int cur = 1;
  long long ans = 0;
  vector<tuple<long long, int, int>> ts;
  for (int i = m - 1; i > 0; --i) {
    cur += can[i];
    if(cur < 0) {
      ans += 1ll * (vals[i - 1] - vals[i]) * cur;
      pa.mergeset(i - 1, i);
    } else if(cur > 0) pa.mergeset(i - 1, i);
    else ts.emplace_back(vals[i] - vals[i - 1], i, i - 1);
  }
  sort(begin(ts), end(ts));
  for (auto &_ : ts) {
    int64_t w;
    int u, v;
    tie(w, u, v) = _;
    if(pa.mergeset(u, v)) {
      ans += w;
    }
  }
  return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 0 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 0 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 0 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 384 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 0 ms 364 KB n = 3
20 Correct 0 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 0 ms 364 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 0 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 0 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 0 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 384 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 0 ms 364 KB n = 3
20 Correct 0 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 0 ms 364 KB n = 8
26 Correct 0 ms 364 KB n = 8
27 Correct 0 ms 364 KB n = 8
28 Correct 0 ms 364 KB n = 8
29 Correct 1 ms 364 KB n = 16
30 Correct 1 ms 364 KB n = 16
31 Correct 0 ms 364 KB n = 16
32 Correct 1 ms 364 KB n = 16
33 Correct 1 ms 364 KB n = 16
34 Correct 0 ms 364 KB n = 16
35 Correct 1 ms 384 KB n = 16
36 Correct 0 ms 364 KB n = 15
37 Correct 1 ms 364 KB n = 8
38 Correct 1 ms 364 KB n = 16
39 Correct 1 ms 364 KB n = 16
40 Correct 1 ms 364 KB n = 9
41 Correct 1 ms 364 KB n = 16
42 Correct 1 ms 364 KB n = 16
43 Correct 0 ms 364 KB n = 16
44 Correct 1 ms 364 KB n = 9
45 Correct 1 ms 364 KB n = 15
46 Correct 1 ms 364 KB n = 16
47 Correct 1 ms 364 KB n = 16
48 Correct 1 ms 364 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 11348 KB n = 199999
2 Correct 232 ms 11476 KB n = 199991
3 Correct 266 ms 11480 KB n = 199993
4 Correct 174 ms 9044 KB n = 152076
5 Correct 90 ms 5724 KB n = 93249
6 Correct 202 ms 10580 KB n = 199910
7 Correct 236 ms 11456 KB n = 199999
8 Correct 194 ms 10708 KB n = 199997
9 Correct 196 ms 9952 KB n = 171294
10 Correct 189 ms 8088 KB n = 140872
11 Correct 203 ms 10836 KB n = 199886
12 Correct 205 ms 12628 KB n = 199996
13 Correct 209 ms 12244 KB n = 200000
14 Correct 230 ms 20692 KB n = 199998
15 Correct 247 ms 20540 KB n = 200000
16 Correct 260 ms 20804 KB n = 199998
17 Correct 230 ms 14672 KB n = 200000
18 Correct 219 ms 11524 KB n = 190000
19 Correct 207 ms 13012 KB n = 177777
20 Correct 91 ms 5980 KB n = 100000
21 Correct 208 ms 11476 KB n = 200000
22 Correct 265 ms 20684 KB n = 200000
23 Correct 256 ms 20692 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 0 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 0 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 0 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 384 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 0 ms 364 KB n = 3
20 Correct 0 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 0 ms 364 KB n = 8
26 Correct 0 ms 364 KB n = 8
27 Correct 0 ms 364 KB n = 8
28 Correct 0 ms 364 KB n = 8
29 Correct 1 ms 364 KB n = 16
30 Correct 1 ms 364 KB n = 16
31 Correct 0 ms 364 KB n = 16
32 Correct 1 ms 364 KB n = 16
33 Correct 1 ms 364 KB n = 16
34 Correct 0 ms 364 KB n = 16
35 Correct 1 ms 384 KB n = 16
36 Correct 0 ms 364 KB n = 15
37 Correct 1 ms 364 KB n = 8
38 Correct 1 ms 364 KB n = 16
39 Correct 1 ms 364 KB n = 16
40 Correct 1 ms 364 KB n = 9
41 Correct 1 ms 364 KB n = 16
42 Correct 1 ms 364 KB n = 16
43 Correct 0 ms 364 KB n = 16
44 Correct 1 ms 364 KB n = 9
45 Correct 1 ms 364 KB n = 15
46 Correct 1 ms 364 KB n = 16
47 Correct 1 ms 364 KB n = 16
48 Correct 1 ms 364 KB n = 16
49 Correct 228 ms 11348 KB n = 199999
50 Correct 232 ms 11476 KB n = 199991
51 Correct 266 ms 11480 KB n = 199993
52 Correct 174 ms 9044 KB n = 152076
53 Correct 90 ms 5724 KB n = 93249
54 Correct 202 ms 10580 KB n = 199910
55 Correct 236 ms 11456 KB n = 199999
56 Correct 194 ms 10708 KB n = 199997
57 Correct 196 ms 9952 KB n = 171294
58 Correct 189 ms 8088 KB n = 140872
59 Correct 203 ms 10836 KB n = 199886
60 Correct 205 ms 12628 KB n = 199996
61 Correct 209 ms 12244 KB n = 200000
62 Correct 230 ms 20692 KB n = 199998
63 Correct 247 ms 20540 KB n = 200000
64 Correct 260 ms 20804 KB n = 199998
65 Correct 230 ms 14672 KB n = 200000
66 Correct 219 ms 11524 KB n = 190000
67 Correct 207 ms 13012 KB n = 177777
68 Correct 91 ms 5980 KB n = 100000
69 Correct 208 ms 11476 KB n = 200000
70 Correct 265 ms 20684 KB n = 200000
71 Correct 256 ms 20692 KB n = 200000
72 Correct 268 ms 15188 KB n = 200000
73 Correct 261 ms 15188 KB n = 200000
74 Correct 220 ms 15184 KB n = 200000
75 Correct 214 ms 15136 KB n = 200000
76 Correct 201 ms 15188 KB n = 200000
77 Correct 194 ms 12884 KB n = 200000
78 Correct 197 ms 22228 KB n = 200000
79 Correct 206 ms 13780 KB n = 184307
80 Correct 92 ms 5980 KB n = 76040
81 Correct 193 ms 13396 KB n = 199981
82 Correct 207 ms 15640 KB n = 199994
83 Correct 207 ms 14676 KB n = 199996
84 Correct 240 ms 23676 KB n = 199998
85 Correct 222 ms 23380 KB n = 200000
86 Correct 226 ms 23892 KB n = 199998
87 Correct 221 ms 18388 KB n = 200000
88 Correct 219 ms 15700 KB n = 200000
89 Correct 213 ms 18368 KB n = 200000
90 Correct 214 ms 15316 KB n = 200000
91 Correct 256 ms 24404 KB n = 200000
92 Correct 259 ms 24532 KB n = 200000