oj.uz

Submission #948927

# Submission time Handle Problem Language Result Execution time Memory
948927 2024-03-18T16:39:05 Z mariaclara Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 602 ms 58864 KB 
#include "railroad.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int pai[MAXN], sz[MAXN];

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;
    if(sz[x] <= sz[y]) {
        pai[x] = y;
        sz[y] += sz[x];
    }
    else {
        pai[y] = x;
        sz[x] += sz[y];
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    map<int,int> corr;
    set<int> numbers;
    vector<int> vel;
    
    for(int i = 0; i < (int)s.size(); i++)
        numbers.insert(s[i]), numbers.insert(t[i]);
    
    for(auto it : numbers) {
        corr[it] = vel.size();
        vel.pb(it);
    }

    // corr[num] = pos
    // vel[pos] = num

    int n = vel.size();
    vector<int> in(n), out(n);

    for(int i = 0; i < n; i++)
        pai[i] = i, sz[i] = 1;

    for(int i = 0; i < (int)s.size(); i++) {
        int u = corr[s[i]], v = corr[t[i]];
        out[u]++;
        in[v]++;
        join(u,v);
    }

    join(0, n-1);
    in[0]++;
    out[n-1]++;
    
    ll ans = 0;
    vector<pii> edges;

    for(int i = 0; i < n-1; i++) {
        if(out[i] - in[i] > 0) {
            ans += (ll)(vel[i+1]-vel[i])*(ll)(out[i]-in[i]);
            out[i+1] += (out[i] - in[i]);
            in[i] = out[i];
            join(i, i+1);
        }
        else if(out[i] - in[i] < 0) {
            in[i+1] += in[i] - out[i];
            out[i] = in[i];
            join(i, i+1);
        }
        edges.pb({vel[i+1]-vel[i], i});
    }

    sort(all(edges));

    for(auto [cost, u] : edges) {
        if(find(u) != find(u+1)) 
            join(u,u+1), ans += cost;
    }

    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 54128 KB n = 199999
2 Correct 562 ms 54852 KB n = 199991
3 Correct 554 ms 54652 KB n = 199993
4 Correct 417 ms 42588 KB n = 152076
5 Correct 186 ms 26092 KB n = 93249
6 Correct 406 ms 46032 KB n = 199910
7 Correct 491 ms 52736 KB n = 199999
8 Correct 437 ms 45344 KB n = 199997
9 Correct 464 ms 46828 KB n = 171294
10 Correct 342 ms 40000 KB n = 140872
11 Correct 403 ms 47568 KB n = 199886
12 Correct 454 ms 53060 KB n = 199996
13 Correct 415 ms 48080 KB n = 200000
14 Correct 400 ms 52176 KB n = 199998
15 Correct 478 ms 53376 KB n = 200000
16 Correct 446 ms 53964 KB n = 199998
17 Correct 514 ms 53316 KB n = 200000
18 Correct 510 ms 52544 KB n = 190000
19 Correct 500 ms 48196 KB n = 177777
20 Correct 190 ms 27464 KB n = 100000
21 Correct 483 ms 54596 KB n = 200000
22 Correct 488 ms 54856 KB n = 200000
23 Correct 542 ms 54140 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2804 KB n = 2
3 Correct 1 ms 2396 KB n = 2
4 Correct 1 ms 2392 KB n = 2
5 Correct 1 ms 2648 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2396 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2392 KB n = 8
14 Correct 1 ms 2396 KB n = 8
15 Correct 2 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2396 KB n = 8
18 Correct 1 ms 2396 KB n = 8
19 Correct 0 ms 2396 KB n = 3
20 Correct 1 ms 2396 KB n = 7
21 Correct 1 ms 2396 KB n = 8
22 Correct 1 ms 2396 KB n = 8
23 Correct 0 ms 2396 KB n = 8
24 Correct 1 ms 2396 KB n = 8
25 Correct 1 ms 2396 KB n = 8
26 Correct 1 ms 2396 KB n = 8
27 Correct 1 ms 2396 KB n = 8
28 Correct 1 ms 2396 KB n = 8
29 Correct 1 ms 2392 KB n = 16
30 Correct 1 ms 2396 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2396 KB n = 16
33 Correct 1 ms 2392 KB n = 16
34 Correct 1 ms 2392 KB n = 16
35 Correct 1 ms 2396 KB n = 16
36 Correct 0 ms 2396 KB n = 15
37 Correct 1 ms 2396 KB n = 8
38 Correct 1 ms 2396 KB n = 16
39 Correct 1 ms 2396 KB n = 16
40 Correct 0 ms 2396 KB n = 9
41 Correct 1 ms 2396 KB n = 16
42 Correct 0 ms 2396 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 0 ms 2396 KB n = 9
45 Correct 1 ms 2396 KB n = 15
46 Correct 1 ms 2396 KB n = 16
47 Correct 0 ms 2396 KB n = 16
48 Correct 1 ms 2396 KB n = 16
49 Correct 602 ms 54128 KB n = 199999
50 Correct 562 ms 54852 KB n = 199991
51 Correct 554 ms 54652 KB n = 199993
52 Correct 417 ms 42588 KB n = 152076
53 Correct 186 ms 26092 KB n = 93249
54 Correct 406 ms 46032 KB n = 199910
55 Correct 491 ms 52736 KB n = 199999
56 Correct 437 ms 45344 KB n = 199997
57 Correct 464 ms 46828 KB n = 171294
58 Correct 342 ms 40000 KB n = 140872
59 Correct 403 ms 47568 KB n = 199886
60 Correct 454 ms 53060 KB n = 199996
61 Correct 415 ms 48080 KB n = 200000
62 Correct 400 ms 52176 KB n = 199998
63 Correct 478 ms 53376 KB n = 200000
64 Correct 446 ms 53964 KB n = 199998
65 Correct 514 ms 53316 KB n = 200000
66 Correct 510 ms 52544 KB n = 190000
67 Correct 500 ms 48196 KB n = 177777
68 Correct 190 ms 27464 KB n = 100000
69 Correct 483 ms 54596 KB n = 200000
70 Correct 488 ms 54856 KB n = 200000
71 Correct 542 ms 54140 KB n = 200000
72 Correct 562 ms 53956 KB n = 200000
73 Correct 539 ms 53316 KB n = 200000
74 Correct 558 ms 53444 KB n = 200000
75 Correct 549 ms 56904 KB n = 200000
76 Correct 526 ms 58564 KB n = 200000
77 Correct 240 ms 33100 KB n = 200000
78 Correct 239 ms 33120 KB n = 200000
79 Correct 488 ms 54016 KB n = 184307
80 Correct 138 ms 23372 KB n = 76040
81 Correct 401 ms 50760 KB n = 199981
82 Correct 431 ms 56388 KB n = 199994
83 Correct 392 ms 50904 KB n = 199996
84 Correct 432 ms 56332 KB n = 199998
85 Correct 407 ms 55108 KB n = 200000
86 Correct 448 ms 56904 KB n = 199998
87 Correct 503 ms 58864 KB n = 200000
88 Correct 528 ms 58164 KB n = 200000
89 Correct 563 ms 58436 KB n = 200000
90 Correct 485 ms 57672 KB n = 200000
91 Correct 476 ms 58436 KB n = 200000
92 Correct 532 ms 58692 KB n = 200000