oj.uz

Submission #915295

# Submission time Handle Problem Language Result Execution time Memory
915295 2024-01-23T16:06:35 Z winter0101 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 895 ms 40380 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=4e5+9;
int f[maxn];
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
map<int,int>ns;
int unite(int u,int v,int w){
u=ns[u],v=ns[v];
u=fs(u),v=fs(v);
if (u==v)return 0;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
f[v]=u;
return w;
}
int a[maxn];//i to i+1
void add(int u,int v){
u=ns[u],v=ns[v];
if (u>v){
a[v]--;
a[u]++;
}
else {
a[u]++;
a[v]--;
}
}
const int inf=1e9;
struct edg{
int u,v,w;
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<int>b;
    b.pb(1),b.pb(inf);
    for1(i,0,n-1){
    b.pb(s[i]);
    b.pb(t[i]);
    }
    sort(all(b));
    b.resize(distance(b.begin(),unique(all(b))));
    for1(i,0,sz(b)-1)ns[b[i]]=i+1;
    int m=sz(b);
    for1(i,1,m)f[i]=-1;
    unite(1,inf,0);
    add(inf,1);
    for1(i,0,n-1){
    add(s[i],t[i]);
    unite(s[i],t[i],0);
    }
    for1(i,1,m)a[i]+=a[i-1];
    long long ans=0;
    for1(i,1,m-1){
    if (a[i]>0){
    ans+=1ll*a[i]*(b[i]-b[i-1]);
    }
    if (a[i]!=0){
    unite(b[i-1],b[i],0);
    }
    }
    vector<edg>temp;
    for1(i,1,m-1){
    temp.pb({b[i-1],b[i],b[i]-b[i-1]});
    }
    sort(all(temp),[](const edg p,const edg q){
    return p.w<q.w;
    });
    for(auto v:temp){
    ans+=unite(v.u,v.v,v.w);
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2392 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 1 ms 2504 KB n = 3
8 Correct 1 ms 2648 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2496 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 2496 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2396 KB n = 8
18 Correct 1 ms 2392 KB n = 8
19 Correct 1 ms 2396 KB n = 3
20 Correct 1 ms 2396 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 2396 KB n = 8
25 Correct 1 ms 2396 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2392 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 1 ms 2504 KB n = 3
8 Correct 1 ms 2648 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2496 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 2496 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2396 KB n = 8
18 Correct 1 ms 2392 KB n = 8
19 Correct 1 ms 2396 KB n = 3
20 Correct 1 ms 2396 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 2396 KB n = 8
25 Correct 1 ms 2396 KB n = 8
26 Correct 1 ms 2392 KB n = 8
27 Correct 1 ms 2396 KB n = 8
28 Correct 1 ms 2492 KB n = 8
29 Correct 1 ms 2392 KB n = 16
30 Correct 1 ms 2396 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2392 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 2396 KB n = 16
39 Correct 1 ms 2496 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2396 KB n = 16
42 Correct 1 ms 2392 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2396 KB n = 9
45 Correct 1 ms 2392 KB n = 15
46 Correct 1 ms 2396 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 832 ms 39872 KB n = 199999
2 Correct 851 ms 39360 KB n = 199991
3 Correct 812 ms 38604 KB n = 199993
4 Correct 575 ms 31580 KB n = 152076
5 Correct 253 ms 19140 KB n = 93249
6 Correct 514 ms 34508 KB n = 199910
7 Correct 768 ms 38952 KB n = 199999
8 Correct 590 ms 33920 KB n = 199997
9 Correct 769 ms 34776 KB n = 171294
10 Correct 499 ms 31936 KB n = 140872
11 Correct 619 ms 35912 KB n = 199886
12 Correct 805 ms 38724 KB n = 199996
13 Correct 601 ms 36800 KB n = 200000
14 Correct 737 ms 38060 KB n = 199998
15 Correct 693 ms 38756 KB n = 200000
16 Correct 842 ms 38076 KB n = 199998
17 Correct 866 ms 38592 KB n = 200000
18 Correct 856 ms 38692 KB n = 190000
19 Correct 662 ms 35776 KB n = 177777
20 Correct 268 ms 20292 KB n = 100000
21 Correct 791 ms 38848 KB n = 200000
22 Correct 760 ms 39084 KB n = 200000
23 Correct 689 ms 39360 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 1 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2392 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 1 ms 2504 KB n = 3
8 Correct 1 ms 2648 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2496 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 2496 KB n = 8
15 Correct 1 ms 2396 KB n = 8
16 Correct 1 ms 2396 KB n = 8
17 Correct 1 ms 2396 KB n = 8
18 Correct 1 ms 2392 KB n = 8
19 Correct 1 ms 2396 KB n = 3
20 Correct 1 ms 2396 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 2396 KB n = 8
25 Correct 1 ms 2396 KB n = 8
26 Correct 1 ms 2392 KB n = 8
27 Correct 1 ms 2396 KB n = 8
28 Correct 1 ms 2492 KB n = 8
29 Correct 1 ms 2392 KB n = 16
30 Correct 1 ms 2396 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2392 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 2396 KB n = 16
39 Correct 1 ms 2496 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2396 KB n = 16
42 Correct 1 ms 2392 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2396 KB n = 9
45 Correct 1 ms 2392 KB n = 15
46 Correct 1 ms 2396 KB n = 16
47 Correct 1 ms 2396 KB n = 16
48 Correct 1 ms 2396 KB n = 16
49 Correct 832 ms 39872 KB n = 199999
50 Correct 851 ms 39360 KB n = 199991
51 Correct 812 ms 38604 KB n = 199993
52 Correct 575 ms 31580 KB n = 152076
53 Correct 253 ms 19140 KB n = 93249
54 Correct 514 ms 34508 KB n = 199910
55 Correct 768 ms 38952 KB n = 199999
56 Correct 590 ms 33920 KB n = 199997
57 Correct 769 ms 34776 KB n = 171294
58 Correct 499 ms 31936 KB n = 140872
59 Correct 619 ms 35912 KB n = 199886
60 Correct 805 ms 38724 KB n = 199996
61 Correct 601 ms 36800 KB n = 200000
62 Correct 737 ms 38060 KB n = 199998
63 Correct 693 ms 38756 KB n = 200000
64 Correct 842 ms 38076 KB n = 199998
65 Correct 866 ms 38592 KB n = 200000
66 Correct 856 ms 38692 KB n = 190000
67 Correct 662 ms 35776 KB n = 177777
68 Correct 268 ms 20292 KB n = 100000
69 Correct 791 ms 38848 KB n = 200000
70 Correct 760 ms 39084 KB n = 200000
71 Correct 689 ms 39360 KB n = 200000
72 Correct 851 ms 38584 KB n = 200000
73 Correct 895 ms 39356 KB n = 200000
74 Correct 868 ms 39104 KB n = 200000
75 Correct 860 ms 39356 KB n = 200000
76 Correct 797 ms 38592 KB n = 200000
77 Correct 366 ms 26304 KB n = 200000
78 Correct 336 ms 25592 KB n = 200000
79 Correct 725 ms 37564 KB n = 184307
80 Correct 197 ms 18112 KB n = 76040
81 Correct 554 ms 36028 KB n = 199981
82 Correct 718 ms 39096 KB n = 199994
83 Correct 623 ms 36544 KB n = 199996
84 Correct 714 ms 38648 KB n = 199998
85 Correct 675 ms 38796 KB n = 200000
86 Correct 778 ms 39372 KB n = 199998
87 Correct 842 ms 38844 KB n = 200000
88 Correct 863 ms 39868 KB n = 200000
89 Correct 865 ms 39104 KB n = 200000
90 Correct 713 ms 40380 KB n = 200000
91 Correct 628 ms 39616 KB n = 200000
92 Correct 703 ms 39112 KB n = 200000