oj.uz

Submission #948926

# Submission time Handle Problem Language Result Execution time Memory
948926 2024-03-18T16:37:51 Z mariaclara Roller Coaster Railroad (IOI16_railroad) C++17
64 / 100
 648 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 += (vel[i+1]-vel[i])*(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 2392 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2488 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2480 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 0 ms 2396 KB n = 3
10 Correct 1 ms 2440 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2396 KB n = 8
14 Correct 1 ms 2396 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2488 KB n = 8
18 Correct 1 ms 2396 KB n = 8
19 Correct 0 ms 2396 KB n = 3
20 Correct 1 ms 2392 KB n = 7
21 Correct 1 ms 2396 KB n = 8
22 Correct 1 ms 2396 KB n = 8
23 Correct 1 ms 2396 KB n = 8
24 Correct 1 ms 2476 KB n = 8
25 Correct 1 ms 2392 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2488 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2480 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 0 ms 2396 KB n = 3
10 Correct 1 ms 2440 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2396 KB n = 8
14 Correct 1 ms 2396 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2488 KB n = 8
18 Correct 1 ms 2396 KB n = 8
19 Correct 0 ms 2396 KB n = 3
20 Correct 1 ms 2392 KB n = 7
21 Correct 1 ms 2396 KB n = 8
22 Correct 1 ms 2396 KB n = 8
23 Correct 1 ms 2396 KB n = 8
24 Correct 1 ms 2476 KB n = 8
25 Correct 1 ms 2392 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 2648 KB n = 16
30 Correct 1 ms 2392 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2396 KB n = 16
33 Correct 1 ms 2396 KB n = 16
34 Correct 1 ms 2396 KB n = 16
35 Correct 1 ms 2396 KB n = 16
36 Correct 1 ms 2396 KB n = 15
37 Correct 1 ms 2396 KB n = 8
38 Correct 1 ms 2492 KB n = 16
39 Correct 1 ms 2396 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2392 KB n = 16
42 Correct 1 ms 2392 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2392 KB n = 9
45 Correct 1 ms 2396 KB n = 15
46 Correct 1 ms 2392 KB n = 16
47 Correct 1 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 539 ms 57064 KB n = 199999
2 Correct 648 ms 58600 KB n = 199991
3 Correct 590 ms 58276 KB n = 199993
4 Correct 364 ms 44520 KB n = 152076
5 Correct 237 ms 27900 KB n = 93249
6 Correct 418 ms 48964 KB n = 199910
7 Correct 497 ms 55532 KB n = 199999
8 Correct 402 ms 49800 KB n = 199997
9 Correct 448 ms 49728 KB n = 171294
10 Correct 324 ms 42580 KB n = 140872
11 Correct 419 ms 49248 KB n = 199886
12 Correct 483 ms 55760 KB n = 199996
13 Correct 425 ms 50500 KB n = 200000
14 Correct 452 ms 56384 KB n = 199998
15 Correct 428 ms 55376 KB n = 200000
16 Correct 450 ms 57944 KB n = 199998
17 Correct 555 ms 58864 KB n = 200000
18 Correct 535 ms 56328 KB n = 190000
19 Correct 426 ms 52808 KB n = 177777
20 Correct 205 ms 29828 KB n = 100000
21 Correct 515 ms 58696 KB n = 200000
22 Correct 486 ms 58396 KB n = 200000
23 Correct 559 ms 57416 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2488 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2480 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 0 ms 2396 KB n = 3
10 Correct 1 ms 2440 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2396 KB n = 8
14 Correct 1 ms 2396 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2488 KB n = 8
18 Correct 1 ms 2396 KB n = 8
19 Correct 0 ms 2396 KB n = 3
20 Correct 1 ms 2392 KB n = 7
21 Correct 1 ms 2396 KB n = 8
22 Correct 1 ms 2396 KB n = 8
23 Correct 1 ms 2396 KB n = 8
24 Correct 1 ms 2476 KB n = 8
25 Correct 1 ms 2392 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 2648 KB n = 16
30 Correct 1 ms 2392 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2396 KB n = 16
33 Correct 1 ms 2396 KB n = 16
34 Correct 1 ms 2396 KB n = 16
35 Correct 1 ms 2396 KB n = 16
36 Correct 1 ms 2396 KB n = 15
37 Correct 1 ms 2396 KB n = 8
38 Correct 1 ms 2492 KB n = 16
39 Correct 1 ms 2396 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2392 KB n = 16
42 Correct 1 ms 2392 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2392 KB n = 9
45 Correct 1 ms 2396 KB n = 15
46 Correct 1 ms 2392 KB n = 16
47 Correct 1 ms 2396 KB n = 16
48 Correct 1 ms 2396 KB n = 16
49 Correct 539 ms 57064 KB n = 199999
50 Correct 648 ms 58600 KB n = 199991
51 Correct 590 ms 58276 KB n = 199993
52 Correct 364 ms 44520 KB n = 152076
53 Correct 237 ms 27900 KB n = 93249
54 Correct 418 ms 48964 KB n = 199910
55 Correct 497 ms 55532 KB n = 199999
56 Correct 402 ms 49800 KB n = 199997
57 Correct 448 ms 49728 KB n = 171294
58 Correct 324 ms 42580 KB n = 140872
59 Correct 419 ms 49248 KB n = 199886
60 Correct 483 ms 55760 KB n = 199996
61 Correct 425 ms 50500 KB n = 200000
62 Correct 452 ms 56384 KB n = 199998
63 Correct 428 ms 55376 KB n = 200000
64 Correct 450 ms 57944 KB n = 199998
65 Correct 555 ms 58864 KB n = 200000
66 Correct 535 ms 56328 KB n = 190000
67 Correct 426 ms 52808 KB n = 177777
68 Correct 205 ms 29828 KB n = 100000
69 Correct 515 ms 58696 KB n = 200000
70 Correct 486 ms 58396 KB n = 200000
71 Correct 559 ms 57416 KB n = 200000
72 Correct 576 ms 57076 KB n = 200000
73 Correct 598 ms 58348 KB n = 200000
74 Incorrect 610 ms 58268 KB answer is not correct: 66605227847128 instead of 66673947323864
75 Halted 0 ms 0 KB -