oj.uz

Submission #54322

# Submission time Handle Problem Language Result Execution time Memory
54322 2018-07-03T07:14:55 Z Alexa2001 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 1419 ms 181952 KB 
#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 4e5 + 5, lim = 1e9;

int n, len[Nmax], t[Nmax], comp[Nmax], balance[Nmax];
map<int, int> mp;
vector<int> v[Nmax];
vector< pair<int, Pair> > edge;

void dfs(int node, int c)
{
    comp[node] = c;
    for(auto it : v[node])
        if(!comp[it]) dfs(it, c);
}

void add_edge_for_apm(int x, int y, int cost)
{
    edge.push_back({ cost, {x, y} });
}

void add_edge(int x, int y)
{
    v[x].push_back(y);
    v[y].push_back(x);
}

int boss(int x)
{
    if(x == t[x]) return x;
    return t[x] = boss(t[x]);
}

void unite(int x, int y)
{
    t[t[x]] = t[y];
}

void APM(ll &ans, int n)
{
    int i;
    for(i=1; i<=n; ++i) t[i] = i;

    sort(edge.begin(), edge.end());
    int x, y, cost;
    for(auto it : edge)
    {
        x = it.second.first;
        y = it.second.second;
        cost = it.first;

        if(boss(x) == boss(y)) continue;
        ans += cost;
        unite(x, y);
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t)
{
    s.push_back(lim);
    t.push_back(1);

    for(auto it : s) mp[it] ++;
    for(auto it : t) mp[it] --;

    int n = 0, sum = 0, prv = 0;
    for(auto &it : mp)
    {
        sum += it.second;
        len[n] = it.first - prv;
        balance[++n] = sum;

        it.second = n;
        prv = it.first;
    }

    ll ans = 0;
    int i;

    for(i=1; i<n; ++i)
        if(balance[i])
        {
            ans += (ll) len[i] * max(0, balance[i]);
            add_edge(i, i+1);
        }

    for(i=0; i<s.size(); ++i)
        add_edge(mp[s[i]], mp[t[i]]);

    int Comp = 0;
    for(i=1; i<=n; ++i)
        if(!comp[i])
            dfs(i, ++Comp);

    for(i=1; i<n; ++i)
        add_edge_for_apm(comp[i], comp[i+1], len[i]);

    APM(ans, Comp);
    return ans;
}

Compilation message

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<s.size(); ++i)
              ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB n = 2
2 Correct 9 ms 9720 KB n = 2
3 Correct 9 ms 9880 KB n = 2
4 Correct 9 ms 9880 KB n = 2
5 Correct 9 ms 9880 KB n = 2
6 Correct 9 ms 10068 KB n = 2
7 Correct 9 ms 10068 KB n = 3
8 Correct 9 ms 10068 KB n = 3
9 Correct 9 ms 10068 KB n = 3
10 Correct 9 ms 10068 KB n = 8
11 Correct 9 ms 10068 KB n = 8
12 Correct 9 ms 10068 KB n = 8
13 Correct 10 ms 10068 KB n = 8
14 Correct 9 ms 10068 KB n = 8
15 Correct 10 ms 10076 KB n = 8
16 Correct 12 ms 10116 KB n = 8
17 Correct 12 ms 10120 KB n = 8
18 Correct 10 ms 10124 KB n = 8
19 Correct 10 ms 10180 KB n = 3
20 Correct 10 ms 10180 KB n = 7
21 Correct 9 ms 10180 KB n = 8
22 Correct 10 ms 10180 KB n = 8
23 Correct 10 ms 10180 KB n = 8
24 Correct 11 ms 10180 KB n = 8
25 Correct 9 ms 10180 KB n = 8

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 68100 KB n = 199999
2 Correct 1222 ms 68100 KB n = 199991
3 Correct 1214 ms 68100 KB n = 199993
4 Correct 1002 ms 68100 KB n = 152076
5 Correct 496 ms 68100 KB n = 93249
6 Correct 1065 ms 68100 KB n = 199910
7 Correct 999 ms 68100 KB n = 199999
8 Correct 907 ms 68100 KB n = 199997
9 Correct 922 ms 68100 KB n = 171294
10 Correct 797 ms 68100 KB n = 140872
11 Correct 1078 ms 68100 KB n = 199886
12 Correct 1309 ms 68100 KB n = 199996
13 Correct 1118 ms 68100 KB n = 200000
14 Correct 1018 ms 73228 KB n = 199998
15 Correct 1012 ms 73912 KB n = 200000
16 Correct 1036 ms 78392 KB n = 199998
17 Correct 1193 ms 87536 KB n = 200000
18 Correct 1033 ms 87536 KB n = 190000
19 Correct 936 ms 89560 KB n = 177777
20 Correct 491 ms 89560 KB n = 100000
21 Correct 1084 ms 100396 KB n = 200000
22 Correct 972 ms 100396 KB n = 200000
23 Correct 1069 ms 108360 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB n = 2
2 Correct 9 ms 9720 KB n = 2
3 Correct 9 ms 9880 KB n = 2
4 Correct 9 ms 9880 KB n = 2
5 Correct 9 ms 9880 KB n = 2
6 Correct 9 ms 10068 KB n = 2
7 Correct 9 ms 10068 KB n = 3
8 Correct 9 ms 10068 KB n = 3
9 Correct 9 ms 10068 KB n = 3
10 Correct 9 ms 10068 KB n = 8
11 Correct 9 ms 10068 KB n = 8
12 Correct 9 ms 10068 KB n = 8
13 Correct 10 ms 10068 KB n = 8
14 Correct 9 ms 10068 KB n = 8
15 Correct 10 ms 10076 KB n = 8
16 Correct 12 ms 10116 KB n = 8
17 Correct 12 ms 10120 KB n = 8
18 Correct 10 ms 10124 KB n = 8
19 Correct 10 ms 10180 KB n = 3
20 Correct 10 ms 10180 KB n = 7
21 Correct 9 ms 10180 KB n = 8
22 Correct 10 ms 10180 KB n = 8
23 Correct 10 ms 10180 KB n = 8
24 Correct 11 ms 10180 KB n = 8
25 Correct 9 ms 10180 KB n = 8
26 Correct 9 ms 10180 KB n = 8
27 Correct 12 ms 10180 KB n = 8
28 Correct 9 ms 10180 KB n = 8
29 Correct 9 ms 10180 KB n = 16
30 Correct 12 ms 10180 KB n = 16
31 Correct 10 ms 10180 KB n = 16
32 Correct 10 ms 10180 KB n = 16
33 Correct 11 ms 10180 KB n = 16
34 Correct 10 ms 10180 KB n = 16
35 Correct 11 ms 10180 KB n = 16
36 Correct 11 ms 10180 KB n = 15
37 Correct 10 ms 10180 KB n = 8
38 Correct 10 ms 10180 KB n = 16
39 Correct 10 ms 10180 KB n = 16
40 Correct 12 ms 10180 KB n = 9
41 Correct 10 ms 10180 KB n = 16
42 Correct 9 ms 10180 KB n = 16
43 Correct 11 ms 10180 KB n = 16
44 Correct 9 ms 10180 KB n = 9
45 Correct 9 ms 10180 KB n = 15
46 Correct 11 ms 10180 KB n = 16
47 Correct 9 ms 10180 KB n = 16
48 Correct 10 ms 10180 KB n = 16
49 Correct 1419 ms 68100 KB n = 199999
50 Correct 1222 ms 68100 KB n = 199991
51 Correct 1214 ms 68100 KB n = 199993
52 Correct 1002 ms 68100 KB n = 152076
53 Correct 496 ms 68100 KB n = 93249
54 Correct 1065 ms 68100 KB n = 199910
55 Correct 999 ms 68100 KB n = 199999
56 Correct 907 ms 68100 KB n = 199997
57 Correct 922 ms 68100 KB n = 171294
58 Correct 797 ms 68100 KB n = 140872
59 Correct 1078 ms 68100 KB n = 199886
60 Correct 1309 ms 68100 KB n = 199996
61 Correct 1118 ms 68100 KB n = 200000
62 Correct 1018 ms 73228 KB n = 199998
63 Correct 1012 ms 73912 KB n = 200000
64 Correct 1036 ms 78392 KB n = 199998
65 Correct 1193 ms 87536 KB n = 200000
66 Correct 1033 ms 87536 KB n = 190000
67 Correct 936 ms 89560 KB n = 177777
68 Correct 491 ms 89560 KB n = 100000
69 Correct 1084 ms 100396 KB n = 200000
70 Correct 972 ms 100396 KB n = 200000
71 Correct 1069 ms 108360 KB n = 200000
72 Correct 1083 ms 112180 KB n = 200000
73 Correct 1149 ms 115808 KB n = 200000
74 Correct 1145 ms 119968 KB n = 200000
75 Correct 1074 ms 123972 KB n = 200000
76 Correct 973 ms 127756 KB n = 200000
77 Correct 650 ms 127756 KB n = 200000
78 Correct 588 ms 127756 KB n = 200000
79 Correct 1062 ms 135420 KB n = 184307
80 Correct 309 ms 135420 KB n = 76040
81 Correct 1016 ms 135420 KB n = 199981
82 Correct 1156 ms 142772 KB n = 199994
83 Correct 1051 ms 142772 KB n = 199996
84 Correct 1075 ms 148072 KB n = 199998
85 Correct 1112 ms 148812 KB n = 200000
86 Correct 1166 ms 153256 KB n = 199998
87 Correct 1110 ms 162516 KB n = 200000
88 Correct 1224 ms 162516 KB n = 200000
89 Correct 1087 ms 170280 KB n = 200000
90 Correct 1044 ms 174084 KB n = 200000
91 Correct 1014 ms 174084 KB n = 200000
92 Correct 1318 ms 181952 KB n = 200000