oj.uz

Submission #915302

# Submission time Handle Problem Language Result Execution time Memory
915302 2024-01-23T16:14:08 Z winter0101 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 821 ms 40084 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;
};
/*
voi 1 dap an thoa man thi ta se noi dinh cuoi them voi dinh s=1e9 t=1 cost se khong doi
nhan xet la neu ta dung do thi voi s->t thi xet i->i+1 thi so lan i->i+1 = so lan i+1->i vi neu khong se khong the tu 1 quay ve 1 duoc
thi ta nhan xet ta co the dung them so canh i->i+1 tuy y vi no tuong duong voi van toc hien tai dang <= s tiep theo thi ta tang no ngang=s cung duoc
con voi moi 1 canh i+1->i thi se +1 vao dap an vi no tuong duong duong ray giam toc do
neu do thi da thoa man dieu kien tren ma van chua lien thong thi ta co the add them 1 canh i->j va j->i voi i j thuoc 2 tplt khac nhau cost la abs(j-i)
tu day bai toan thanh tim mst cho do thi
*/
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 2648 KB n = 2
3 Correct 1 ms 2392 KB n = 2
4 Correct 1 ms 2392 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2396 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2392 KB n = 8
14 Correct 1 ms 2396 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 2648 KB n = 8
24 Correct 1 ms 2392 KB n = 8
25 Correct 1 ms 2392 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 2648 KB n = 2
3 Correct 1 ms 2392 KB n = 2
4 Correct 1 ms 2392 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2396 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2392 KB n = 8
14 Correct 1 ms 2396 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 2648 KB n = 8
24 Correct 1 ms 2392 KB n = 8
25 Correct 1 ms 2392 KB n = 8
26 Correct 1 ms 2392 KB n = 8
27 Correct 1 ms 2392 KB n = 8
28 Correct 1 ms 2396 KB n = 8
29 Correct 1 ms 2396 KB n = 16
30 Correct 1 ms 2392 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2396 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 2396 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2396 KB n = 16
42 Correct 1 ms 2396 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2396 KB n = 9
45 Correct 1 ms 2396 KB n = 15
46 Correct 1 ms 2396 KB n = 16
47 Correct 1 ms 2392 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 767 ms 38820 KB n = 199999
2 Correct 791 ms 38060 KB n = 199991
3 Correct 761 ms 38568 KB n = 199993
4 Correct 465 ms 31032 KB n = 152076
5 Correct 279 ms 20092 KB n = 93249
6 Correct 485 ms 34532 KB n = 199910
7 Correct 607 ms 38020 KB n = 199999
8 Correct 470 ms 33980 KB n = 199997
9 Correct 608 ms 33968 KB n = 171294
10 Correct 453 ms 30912 KB n = 140872
11 Correct 459 ms 34380 KB n = 199886
12 Correct 676 ms 38592 KB n = 199996
13 Correct 476 ms 36020 KB n = 200000
14 Correct 545 ms 36796 KB n = 199998
15 Correct 537 ms 37824 KB n = 200000
16 Correct 624 ms 37972 KB n = 199998
17 Correct 702 ms 38076 KB n = 200000
18 Correct 636 ms 37320 KB n = 190000
19 Correct 592 ms 36816 KB n = 177777
20 Correct 280 ms 20164 KB n = 100000
21 Correct 714 ms 39096 KB n = 200000
22 Correct 582 ms 38808 KB n = 200000
23 Correct 651 ms 39336 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 2648 KB n = 2
3 Correct 1 ms 2392 KB n = 2
4 Correct 1 ms 2392 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2392 KB n = 2
7 Correct 1 ms 2396 KB n = 3
8 Correct 1 ms 2396 KB n = 3
9 Correct 1 ms 2396 KB n = 3
10 Correct 1 ms 2396 KB n = 8
11 Correct 1 ms 2396 KB n = 8
12 Correct 1 ms 2396 KB n = 8
13 Correct 1 ms 2392 KB n = 8
14 Correct 1 ms 2396 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 2648 KB n = 8
24 Correct 1 ms 2392 KB n = 8
25 Correct 1 ms 2392 KB n = 8
26 Correct 1 ms 2392 KB n = 8
27 Correct 1 ms 2392 KB n = 8
28 Correct 1 ms 2396 KB n = 8
29 Correct 1 ms 2396 KB n = 16
30 Correct 1 ms 2392 KB n = 16
31 Correct 1 ms 2396 KB n = 16
32 Correct 1 ms 2396 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 2396 KB n = 16
40 Correct 1 ms 2396 KB n = 9
41 Correct 1 ms 2396 KB n = 16
42 Correct 1 ms 2396 KB n = 16
43 Correct 1 ms 2396 KB n = 16
44 Correct 1 ms 2396 KB n = 9
45 Correct 1 ms 2396 KB n = 15
46 Correct 1 ms 2396 KB n = 16
47 Correct 1 ms 2392 KB n = 16
48 Correct 1 ms 2396 KB n = 16
49 Correct 767 ms 38820 KB n = 199999
50 Correct 791 ms 38060 KB n = 199991
51 Correct 761 ms 38568 KB n = 199993
52 Correct 465 ms 31032 KB n = 152076
53 Correct 279 ms 20092 KB n = 93249
54 Correct 485 ms 34532 KB n = 199910
55 Correct 607 ms 38020 KB n = 199999
56 Correct 470 ms 33980 KB n = 199997
57 Correct 608 ms 33968 KB n = 171294
58 Correct 453 ms 30912 KB n = 140872
59 Correct 459 ms 34380 KB n = 199886
60 Correct 676 ms 38592 KB n = 199996
61 Correct 476 ms 36020 KB n = 200000
62 Correct 545 ms 36796 KB n = 199998
63 Correct 537 ms 37824 KB n = 200000
64 Correct 624 ms 37972 KB n = 199998
65 Correct 702 ms 38076 KB n = 200000
66 Correct 636 ms 37320 KB n = 190000
67 Correct 592 ms 36816 KB n = 177777
68 Correct 280 ms 20164 KB n = 100000
69 Correct 714 ms 39096 KB n = 200000
70 Correct 582 ms 38808 KB n = 200000
71 Correct 651 ms 39336 KB n = 200000
72 Correct 753 ms 39792 KB n = 200000
73 Correct 694 ms 39336 KB n = 200000
74 Correct 775 ms 40084 KB n = 200000
75 Correct 797 ms 39868 KB n = 200000
76 Correct 821 ms 38848 KB n = 200000
77 Correct 368 ms 24776 KB n = 200000
78 Correct 344 ms 26052 KB n = 200000
79 Correct 626 ms 37612 KB n = 184307
80 Correct 192 ms 17916 KB n = 76040
81 Correct 473 ms 34496 KB n = 199981
82 Correct 626 ms 38208 KB n = 199994
83 Correct 526 ms 34776 KB n = 199996
84 Correct 577 ms 37636 KB n = 199998
85 Correct 575 ms 37824 KB n = 200000
86 Correct 617 ms 37952 KB n = 199998
87 Correct 747 ms 39740 KB n = 200000
88 Correct 751 ms 38848 KB n = 200000
89 Correct 801 ms 37056 KB n = 200000
90 Correct 706 ms 38592 KB n = 200000
91 Correct 636 ms 38552 KB n = 200000
92 Correct 644 ms 37568 KB n = 200000