oj.uz

Submission #469334

# Submission time Handle Problem Language Result Execution time Memory
469334 2021-08-31T13:45:28 Z luciocf Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 874 ms 41668 KB 
#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

typedef long long ll;

const int maxn = 4e5+10;

struct DSU
{
    int pai[maxn], peso[maxn];

    void init(int n)
    {
        for (int i = 0; i < n; i++)
            pai[i] = i, peso[i] = 1;
    }

    int Find(int x)
    {
        if (pai[x] == 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 (peso[x] < peso[y]) swap(x, y);

        pai[y] = x, peso[x] += peso[y];
    }
} dsu;

struct Edge
{
    int u, v, w;

    bool operator< (const Edge o)
    {
        return w < o.w;
    }
};

map<int, int> mp;
int back[maxn];

int soma[maxn];

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    s.push_back(1e9); s.push_back(1);
    int n = (int) s.size();

    for (int i = 0; i < n; i++)
        mp[s[i]] = mp[t[i]] = 0;
    
    int aux = 0;
    for (auto &x: mp)
    {
        x.second = aux++;
        back[aux-1] = x.first;
    }

    ll ans = 0;
    vector<int> v;
    vector<Edge> edge;

    dsu.init(aux);
    for (int i = 0; i < n; i++)
    {
        soma[mp[s[i]]]++;
        soma[mp[t[i]]]--;

        v.push_back(mp[s[i]]);
        v.push_back(mp[t[i]]);

        dsu.Join(mp[s[i]], mp[t[i]]);
    }

    for (int i = 0; i < aux; i++)
    {
        if (i) soma[i] += soma[i-1];

        if (soma[i] > 0)
        {
            dsu.Join(i, i+1);
            ans += 1ll*(back[i+1]-back[i])*soma[i];
        }
        else if (soma[i] < 0) dsu.Join(i, i+1);

        if (i < aux-1) edge.push_back({i, i+1, back[i+1]-back[i]});
    }

    sort(edge.begin(), edge.end());

    for (auto pp: edge)
    {
        int u = pp.u, v = pp.v, w = pp.w;

        if (dsu.Find(u) != dsu.Find(v))
        {
            dsu.Join(u, v);
            ans += 1ll*w;
        }
    }

    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 37696 KB n = 199999
2 Correct 874 ms 37840 KB n = 199991
3 Correct 776 ms 37684 KB n = 199993
4 Correct 566 ms 30552 KB n = 152076
5 Correct 281 ms 18020 KB n = 93249
6 Correct 643 ms 33296 KB n = 199910
7 Correct 644 ms 37308 KB n = 199999
8 Correct 622 ms 33276 KB n = 199997
9 Correct 694 ms 33412 KB n = 171294
10 Correct 529 ms 28872 KB n = 140872
11 Correct 635 ms 33452 KB n = 199886
12 Correct 642 ms 37352 KB n = 199996
13 Correct 598 ms 34220 KB n = 200000
14 Correct 570 ms 37168 KB n = 199998
15 Correct 583 ms 36736 KB n = 200000
16 Correct 611 ms 37560 KB n = 199998
17 Correct 634 ms 37644 KB n = 200000
18 Correct 625 ms 36372 KB n = 190000
19 Correct 541 ms 34424 KB n = 177777
20 Correct 278 ms 19004 KB n = 100000
21 Correct 688 ms 37720 KB n = 200000
22 Correct 699 ms 37732 KB n = 200000
23 Correct 766 ms 37828 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 2
2 Correct 0 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 0 ms 204 KB n = 2
5 Correct 0 ms 204 KB n = 2
6 Correct 0 ms 204 KB n = 2
7 Correct 1 ms 204 KB n = 3
8 Correct 1 ms 204 KB n = 3
9 Correct 0 ms 332 KB n = 3
10 Correct 1 ms 332 KB n = 8
11 Correct 1 ms 332 KB n = 8
12 Correct 1 ms 332 KB n = 8
13 Correct 0 ms 332 KB n = 8
14 Correct 0 ms 332 KB n = 8
15 Correct 1 ms 204 KB n = 8
16 Correct 1 ms 204 KB n = 8
17 Correct 1 ms 332 KB n = 8
18 Correct 1 ms 332 KB n = 8
19 Correct 0 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 332 KB n = 8
22 Correct 1 ms 304 KB n = 8
23 Correct 1 ms 308 KB n = 8
24 Correct 1 ms 332 KB n = 8
25 Correct 1 ms 204 KB n = 8
26 Correct 1 ms 332 KB n = 8
27 Correct 1 ms 332 KB n = 8
28 Correct 0 ms 204 KB n = 8
29 Correct 1 ms 204 KB n = 16
30 Correct 1 ms 204 KB n = 16
31 Correct 1 ms 204 KB n = 16
32 Correct 1 ms 332 KB n = 16
33 Correct 1 ms 204 KB n = 16
34 Correct 1 ms 204 KB n = 16
35 Correct 1 ms 204 KB n = 16
36 Correct 1 ms 332 KB n = 15
37 Correct 0 ms 332 KB n = 8
38 Correct 0 ms 332 KB n = 16
39 Correct 1 ms 204 KB n = 16
40 Correct 1 ms 308 KB n = 9
41 Correct 1 ms 316 KB n = 16
42 Correct 1 ms 204 KB n = 16
43 Correct 1 ms 332 KB n = 16
44 Correct 0 ms 332 KB n = 9
45 Correct 1 ms 332 KB n = 15
46 Correct 1 ms 204 KB n = 16
47 Correct 1 ms 332 KB n = 16
48 Correct 1 ms 308 KB n = 16
49 Correct 781 ms 37696 KB n = 199999
50 Correct 874 ms 37840 KB n = 199991
51 Correct 776 ms 37684 KB n = 199993
52 Correct 566 ms 30552 KB n = 152076
53 Correct 281 ms 18020 KB n = 93249
54 Correct 643 ms 33296 KB n = 199910
55 Correct 644 ms 37308 KB n = 199999
56 Correct 622 ms 33276 KB n = 199997
57 Correct 694 ms 33412 KB n = 171294
58 Correct 529 ms 28872 KB n = 140872
59 Correct 635 ms 33452 KB n = 199886
60 Correct 642 ms 37352 KB n = 199996
61 Correct 598 ms 34220 KB n = 200000
62 Correct 570 ms 37168 KB n = 199998
63 Correct 583 ms 36736 KB n = 200000
64 Correct 611 ms 37560 KB n = 199998
65 Correct 634 ms 37644 KB n = 200000
66 Correct 625 ms 36372 KB n = 190000
67 Correct 541 ms 34424 KB n = 177777
68 Correct 278 ms 19004 KB n = 100000
69 Correct 688 ms 37720 KB n = 200000
70 Correct 699 ms 37732 KB n = 200000
71 Correct 766 ms 37828 KB n = 200000
72 Correct 777 ms 41648 KB n = 200000
73 Correct 784 ms 41652 KB n = 200000
74 Correct 842 ms 41616 KB n = 200000
75 Correct 626 ms 41560 KB n = 200000
76 Correct 635 ms 41536 KB n = 200000
77 Correct 402 ms 26004 KB n = 200000
78 Correct 416 ms 26020 KB n = 200000
79 Correct 662 ms 38860 KB n = 184307
80 Correct 208 ms 17156 KB n = 76040
81 Correct 602 ms 36280 KB n = 199981
82 Correct 612 ms 40488 KB n = 199994
83 Correct 591 ms 37160 KB n = 199996
84 Correct 603 ms 40260 KB n = 199998
85 Correct 586 ms 39852 KB n = 200000
86 Correct 601 ms 41028 KB n = 199998
87 Correct 615 ms 41616 KB n = 200000
88 Correct 640 ms 41544 KB n = 200000
89 Correct 596 ms 41640 KB n = 200000
90 Correct 665 ms 41668 KB n = 200000
91 Correct 689 ms 41592 KB n = 200000
92 Correct 741 ms 41652 KB n = 200000