oj.uz

Submission #316104

# Submission time Handle Problem Language Result Execution time Memory
316104 2020-10-25T08:25:06 Z moonrabbit2 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 346 ms 53736 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];
vector<int> vec;
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++){
		vec.emplace_back(s[i]);
		vec.emplace_back(t[i]);
    }
	vec.emplace_back(1);
	sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());
	c=vec.size();
	for(int i=1;i<=c;i++) from[i]=vec[i-1];
	for(int i=0;i<n;i++){
		s[i]=lower_bound(vec.begin(),vec.end(),s[i])-vec.begin()+1;
		t[i]=lower_bound(vec.begin(),vec.end(),t[i])-vec.begin()+1;
	}
    sum[2]--;
    g1[c].push_back(1);
    for(int i=0;i<n;i++){
		sum[s[i]+1]++;
		sum[t[i]+1]--;
		g1[s[i]].emplace_back(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 9 ms 12032 KB n = 2
2 Correct 8 ms 12032 KB n = 2
3 Correct 8 ms 12032 KB n = 2
4 Correct 9 ms 12032 KB n = 2
5 Correct 8 ms 12032 KB n = 2
6 Correct 8 ms 12032 KB n = 2
7 Correct 8 ms 12032 KB n = 3
8 Correct 8 ms 12032 KB n = 3
9 Correct 9 ms 12032 KB n = 3
10 Correct 9 ms 12032 KB n = 8
11 Correct 9 ms 12032 KB n = 8
12 Correct 9 ms 12160 KB n = 8
13 Correct 9 ms 12032 KB n = 8
14 Correct 9 ms 12032 KB n = 8
15 Correct 9 ms 12032 KB n = 8
16 Correct 9 ms 12032 KB n = 8
17 Correct 9 ms 12032 KB n = 8
18 Correct 8 ms 12032 KB n = 8
19 Correct 9 ms 12032 KB n = 3
20 Correct 9 ms 12032 KB n = 7
21 Correct 9 ms 12032 KB n = 8
22 Correct 9 ms 12160 KB n = 8
23 Correct 9 ms 12032 KB n = 8
24 Correct 8 ms 12032 KB n = 8
25 Correct 9 ms 12032 KB n = 8

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 49668 KB n = 199999
2 Correct 341 ms 42488 KB n = 199991
3 Correct 307 ms 53224 KB n = 199993
4 Correct 235 ms 37608 KB n = 152076
5 Correct 139 ms 28012 KB n = 93249
6 Correct 283 ms 39656 KB n = 199910
7 Correct 283 ms 45800 KB n = 199999
8 Correct 268 ms 41448 KB n = 199997
9 Correct 277 ms 41320 KB n = 171294
10 Correct 224 ms 35944 KB n = 140872
11 Correct 276 ms 39784 KB n = 199886
12 Correct 292 ms 45964 KB n = 199996
13 Correct 277 ms 42472 KB n = 200000
14 Correct 280 ms 49256 KB n = 199998
15 Correct 277 ms 47032 KB n = 200000
16 Correct 282 ms 47860 KB n = 199998
17 Correct 293 ms 47208 KB n = 200000
18 Correct 288 ms 45928 KB n = 190000
19 Correct 266 ms 49000 KB n = 177777
20 Correct 144 ms 29164 KB n = 100000
21 Correct 323 ms 46312 KB n = 200000
22 Correct 323 ms 44648 KB n = 200000
23 Correct 333 ms 53480 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB n = 2
2 Correct 8 ms 12032 KB n = 2
3 Correct 8 ms 12032 KB n = 2
4 Correct 9 ms 12032 KB n = 2
5 Correct 8 ms 12032 KB n = 2
6 Correct 8 ms 12032 KB n = 2
7 Correct 8 ms 12032 KB n = 3
8 Correct 8 ms 12032 KB n = 3
9 Correct 9 ms 12032 KB n = 3
10 Correct 9 ms 12032 KB n = 8
11 Correct 9 ms 12032 KB n = 8
12 Correct 9 ms 12160 KB n = 8
13 Correct 9 ms 12032 KB n = 8
14 Correct 9 ms 12032 KB n = 8
15 Correct 9 ms 12032 KB n = 8
16 Correct 9 ms 12032 KB n = 8
17 Correct 9 ms 12032 KB n = 8
18 Correct 8 ms 12032 KB n = 8
19 Correct 9 ms 12032 KB n = 3
20 Correct 9 ms 12032 KB n = 7
21 Correct 9 ms 12032 KB n = 8
22 Correct 9 ms 12160 KB n = 8
23 Correct 9 ms 12032 KB n = 8
24 Correct 8 ms 12032 KB n = 8
25 Correct 9 ms 12032 KB n = 8
26 Correct 8 ms 12032 KB n = 8
27 Correct 9 ms 12032 KB n = 8
28 Correct 8 ms 12032 KB n = 8
29 Correct 9 ms 12032 KB n = 16
30 Correct 9 ms 12032 KB n = 16
31 Correct 8 ms 12032 KB n = 16
32 Correct 9 ms 12032 KB n = 16
33 Correct 9 ms 12160 KB n = 16
34 Correct 9 ms 12032 KB n = 16
35 Correct 8 ms 12160 KB n = 16
36 Correct 9 ms 12160 KB n = 15
37 Correct 8 ms 12032 KB n = 8
38 Correct 9 ms 12032 KB n = 16
39 Correct 9 ms 12032 KB n = 16
40 Correct 8 ms 12032 KB n = 9
41 Correct 9 ms 12032 KB n = 16
42 Correct 9 ms 12032 KB n = 16
43 Correct 9 ms 12032 KB n = 16
44 Correct 9 ms 12032 KB n = 9
45 Correct 9 ms 12032 KB n = 15
46 Correct 8 ms 12160 KB n = 16
47 Correct 9 ms 12032 KB n = 16
48 Correct 8 ms 12032 KB n = 16
49 Correct 308 ms 49668 KB n = 199999
50 Correct 341 ms 42488 KB n = 199991
51 Correct 307 ms 53224 KB n = 199993
52 Correct 235 ms 37608 KB n = 152076
53 Correct 139 ms 28012 KB n = 93249
54 Correct 283 ms 39656 KB n = 199910
55 Correct 283 ms 45800 KB n = 199999
56 Correct 268 ms 41448 KB n = 199997
57 Correct 277 ms 41320 KB n = 171294
58 Correct 224 ms 35944 KB n = 140872
59 Correct 276 ms 39784 KB n = 199886
60 Correct 292 ms 45964 KB n = 199996
61 Correct 277 ms 42472 KB n = 200000
62 Correct 280 ms 49256 KB n = 199998
63 Correct 277 ms 47032 KB n = 200000
64 Correct 282 ms 47860 KB n = 199998
65 Correct 293 ms 47208 KB n = 200000
66 Correct 288 ms 45928 KB n = 190000
67 Correct 266 ms 49000 KB n = 177777
68 Correct 144 ms 29164 KB n = 100000
69 Correct 323 ms 46312 KB n = 200000
70 Correct 323 ms 44648 KB n = 200000
71 Correct 333 ms 53480 KB n = 200000
72 Correct 306 ms 53480 KB n = 200000
73 Correct 346 ms 46440 KB n = 200000
74 Correct 303 ms 52072 KB n = 200000
75 Correct 298 ms 53644 KB n = 200000
76 Correct 299 ms 53480 KB n = 200000
77 Correct 260 ms 37096 KB n = 200000
78 Correct 254 ms 34792 KB n = 200000
79 Correct 311 ms 42092 KB n = 184307
80 Correct 117 ms 25188 KB n = 76040
81 Correct 279 ms 39788 KB n = 199981
82 Correct 296 ms 45800 KB n = 199994
83 Correct 273 ms 42472 KB n = 199996
84 Correct 280 ms 49356 KB n = 199998
85 Correct 280 ms 47080 KB n = 200000
86 Correct 288 ms 47720 KB n = 199998
87 Correct 288 ms 47336 KB n = 200000
88 Correct 300 ms 47720 KB n = 200000
89 Correct 297 ms 53736 KB n = 200000
90 Correct 324 ms 46440 KB n = 200000
91 Correct 323 ms 44648 KB n = 200000
92 Correct 337 ms 53612 KB n = 200000