oj.uz

Submission #67057

# Submission time Handle Problem Language Result Execution time Memory
67057 2018-08-13T09:27:16 Z moonrabbit2 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 1730 ms 225276 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define N 500005
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct edge{ll c;int u,v;};
int n,c,group[N],c_g,p[N],en,x;
ll ans,sum[N],from[N];
map<int,int> mp,to;
vector<int> g1[N];
edge g2[N];
int fi(int x)
{
    if(p[x]==x)
        return x;
    return p[x]=fi(p[x]);
}
void un(int x,int y)
{
    x=fi(x),y=fi(y);
    if(x==y)
        return;
    p[y]=x;
}
void dfs(int curr)
{
    group[curr]=c_g;
    for(auto &it : g1[curr]){
        if(!group[it])
            dfs(it);
    }
}
bool sortf(edge e1,edge e2){return e1.c<e2.c;}
ll plan_roller_coaster(vector<int> s,vector<int> t)
{
    n=s.size();
    for(int i=0;i<n;i++){
        mp[s[i]]++;
        mp[t[i]]++;
    }
    mp[1]++;
    for(auto &it : mp){
        to[it.first]=++c;
        from[c]=it.first;
    }
    sum[2]--;
    g1[c].push_back(1);
    for(int i=0;i<n;i++){
        if(s[i]==t[i])continue;
        if(s[i]<t[i]){
            sum[to[s[i]]+1]++;
            sum[to[t[i]]+1]--;
        }
        else{
            sum[to[s[i]]+1]++;
            sum[to[t[i]]+1]--;
        }
        g1[to[s[i]]].push_back(to[t[i]]);
    }
    for(int i=2;i<=c;i++){
        sum[i]+=sum[i-1];
        if(sum[i]<0)
            g1[i-1].push_back(i);
        if(sum[i]>0){
            g1[i].push_back(i-1);
            ans+=sum[i]*(from[i]-from[i-1]);
        }
    }
    for(int i=1;i<=c;i++){
        if(group[i])
            continue;
        c_g++;
        p[c_g]=c_g;
        dfs(i);
    }
    for(int i=2;i<=c;i++){
        if(group[i-1]!=group[i]){
            g2[++en]={from[i]-from[i-1],group[i-1],group[i]};
        }
    }
    sort(g2+1,g2+1+en,sortf);
    for(int i=1;i<=en;i++){
        int u=g2[i].u,v=g2[i].v;
        if(fi(u)==fi(v))
            continue;
        ans+=g2[i].c;
        un(u,v);
    }
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 86120 KB n = 199999
2 Correct 1334 ms 86120 KB n = 199991
3 Correct 1447 ms 89632 KB n = 199993
4 Correct 1108 ms 89632 KB n = 152076
5 Correct 536 ms 89632 KB n = 93249
6 Correct 1341 ms 89632 KB n = 199910
7 Correct 1243 ms 92532 KB n = 199999
8 Correct 1238 ms 92532 KB n = 199997
9 Correct 1222 ms 92532 KB n = 171294
10 Correct 917 ms 92532 KB n = 140872
11 Correct 1115 ms 92828 KB n = 199886
12 Correct 1200 ms 107452 KB n = 199996
13 Correct 1130 ms 107452 KB n = 200000
14 Correct 1031 ms 116632 KB n = 199998
15 Correct 1094 ms 116780 KB n = 200000
16 Correct 1173 ms 122016 KB n = 199998
17 Correct 1236 ms 124856 KB n = 200000
18 Correct 1088 ms 125640 KB n = 190000
19 Correct 1087 ms 130168 KB n = 177777
20 Correct 553 ms 130168 KB n = 100000
21 Correct 1267 ms 136912 KB n = 200000
22 Correct 1377 ms 139128 KB n = 200000
23 Correct 1570 ms 151952 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12156 KB n = 2
2 Correct 14 ms 12156 KB n = 2
3 Correct 15 ms 12192 KB n = 2
4 Correct 13 ms 12244 KB n = 2
5 Correct 15 ms 12388 KB n = 2
6 Correct 14 ms 12388 KB n = 2
7 Correct 13 ms 12388 KB n = 3
8 Correct 14 ms 12388 KB n = 3
9 Correct 15 ms 12388 KB n = 3
10 Correct 15 ms 12396 KB n = 8
11 Correct 13 ms 12396 KB n = 8
12 Correct 13 ms 12396 KB n = 8
13 Correct 13 ms 12396 KB n = 8
14 Correct 16 ms 12396 KB n = 8
15 Correct 14 ms 12396 KB n = 8
16 Correct 14 ms 12396 KB n = 8
17 Correct 14 ms 12396 KB n = 8
18 Correct 15 ms 12396 KB n = 8
19 Correct 13 ms 12396 KB n = 3
20 Correct 13 ms 12396 KB n = 7
21 Correct 14 ms 12396 KB n = 8
22 Correct 15 ms 12396 KB n = 8
23 Correct 13 ms 12396 KB n = 8
24 Correct 15 ms 12396 KB n = 8
25 Correct 13 ms 12396 KB n = 8
26 Correct 15 ms 12396 KB n = 8
27 Correct 15 ms 12396 KB n = 8
28 Correct 12 ms 12396 KB n = 8
29 Correct 12 ms 12396 KB n = 16
30 Correct 12 ms 12400 KB n = 16
31 Correct 13 ms 12400 KB n = 16
32 Correct 13 ms 12400 KB n = 16
33 Correct 13 ms 12400 KB n = 16
34 Correct 14 ms 12400 KB n = 16
35 Correct 12 ms 12400 KB n = 16
36 Correct 13 ms 12400 KB n = 15
37 Correct 15 ms 12400 KB n = 8
38 Correct 14 ms 12400 KB n = 16
39 Correct 12 ms 12400 KB n = 16
40 Correct 12 ms 12400 KB n = 9
41 Correct 13 ms 12400 KB n = 16
42 Correct 13 ms 12400 KB n = 16
43 Correct 12 ms 12400 KB n = 16
44 Correct 14 ms 12412 KB n = 9
45 Correct 14 ms 12412 KB n = 15
46 Correct 15 ms 12412 KB n = 16
47 Correct 13 ms 12412 KB n = 16
48 Correct 14 ms 12412 KB n = 16
49 Correct 1313 ms 86120 KB n = 199999
50 Correct 1334 ms 86120 KB n = 199991
51 Correct 1447 ms 89632 KB n = 199993
52 Correct 1108 ms 89632 KB n = 152076
53 Correct 536 ms 89632 KB n = 93249
54 Correct 1341 ms 89632 KB n = 199910
55 Correct 1243 ms 92532 KB n = 199999
56 Correct 1238 ms 92532 KB n = 199997
57 Correct 1222 ms 92532 KB n = 171294
58 Correct 917 ms 92532 KB n = 140872
59 Correct 1115 ms 92828 KB n = 199886
60 Correct 1200 ms 107452 KB n = 199996
61 Correct 1130 ms 107452 KB n = 200000
62 Correct 1031 ms 116632 KB n = 199998
63 Correct 1094 ms 116780 KB n = 200000
64 Correct 1173 ms 122016 KB n = 199998
65 Correct 1236 ms 124856 KB n = 200000
66 Correct 1088 ms 125640 KB n = 190000
67 Correct 1087 ms 130168 KB n = 177777
68 Correct 553 ms 130168 KB n = 100000
69 Correct 1267 ms 136912 KB n = 200000
70 Correct 1377 ms 139128 KB n = 200000
71 Correct 1570 ms 151952 KB n = 200000
72 Correct 1579 ms 155680 KB n = 200000
73 Correct 1563 ms 155680 KB n = 200000
74 Correct 1730 ms 161788 KB n = 200000
75 Correct 1513 ms 167284 KB n = 200000
76 Correct 1427 ms 171188 KB n = 200000
77 Correct 473 ms 171188 KB n = 200000
78 Correct 448 ms 171188 KB n = 200000
79 Correct 1401 ms 171188 KB n = 184307
80 Correct 469 ms 171188 KB n = 76040
81 Correct 1211 ms 171188 KB n = 199981
82 Correct 1145 ms 182232 KB n = 199994
83 Correct 1216 ms 182232 KB n = 199996
84 Correct 1100 ms 191332 KB n = 199998
85 Correct 1178 ms 191612 KB n = 200000
86 Correct 1214 ms 196716 KB n = 199998
87 Correct 1483 ms 199740 KB n = 200000
88 Correct 1394 ms 203952 KB n = 200000
89 Correct 1371 ms 213648 KB n = 200000
90 Correct 1371 ms 213648 KB n = 200000
91 Correct 1328 ms 213648 KB n = 200000
92 Correct 1489 ms 225276 KB n = 200000