oj.uz

답안 #616756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
616756 2022-08-01T06:39:11 Z rrrr10000 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 268 ms 35340 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;
const ll INF=1001001001;
struct UF{
    ll n;
    vi par,sz;
    UF(ll n_):n(n_),par(n_,-1),sz(n_,1){}
    ll root(ll i){
        if(par[i]==-1)return i;
        return root(par[i]);
    }
    bool merge(ll a,ll b){
        a=root(a);b=root(b);
        if(a==b)return false;
        if(sz[a]>sz[b])swap(a,b);
        par[a]=b;sz[b]+=sz[a];
        return true;
    }
};
long long plan_roller_coaster1(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vp v(n);rep(i,n)v[i]=P(s[i],t[i]);
    vvi dp(1<<n,vi(n,inf));
    rep(i,n)dp[1<<i][i]=0;
    REP(bit,1,1<<n)rep(i,n)if(dp[bit][i]!=inf){
        rep(j,n)if(!(bit>>j&1))chmin(dp[bit|(1<<j)][j],dp[bit][i]+max(0ll,v[i].se-v[j].fi));
    }
    ll ans=inf;
    rep(i,n)chmin(ans,dp.back()[i]);
    return ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vp v(n);rep(i,n)v[i]=P(s[i],t[i]);
    vi srt;srt.pb(0);srt.pb(INF);
    rep(i,n){
        srt.pb(v[i].fi);srt.pb(v[i].se);
    }
    dupli(srt);
    vi imos(srt.size());
    rep(i,n){
        v[i].fi=lb(srt,v[i].fi);v[i].se=lb(srt,v[i].se);
    }
    v.pb(srt.size()-1,0);
    for(auto x:v){
        imos[x.fi]++;imos[x.se]--;
    }
    rep(i,imos.size()-1)imos[i+1]+=imos[i];
    ll ans=0;
    rep(i,imos.size()-1)ans+=max(0ll,imos[i])*(srt[i+1]-srt[i]);
    UF uf(srt.size());
    rep(i,imos.size()-1)if(imos[i]!=0)uf.merge(i,i+1);
    for(auto x:v)uf.merge(x.fi,x.se);
    vp edge;
    rep(i,srt.size()-1)edge.pb(srt[i+1]-srt[i],i);
    sort(all(edge));
    for(auto x:edge)if(uf.merge(x.se,x.se+1))ans+=x.fi;
    return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 300 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 340 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 296 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 300 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 300 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 300 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 232 KB n = 8
25 Correct 1 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 300 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 340 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 296 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 300 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 300 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 300 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 232 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 296 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 260 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 328 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 296 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 256 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 35260 KB n = 199999
2 Correct 236 ms 35216 KB n = 199991
3 Correct 252 ms 35184 KB n = 199993
4 Correct 159 ms 29572 KB n = 152076
5 Correct 94 ms 16948 KB n = 93249
6 Correct 193 ms 32340 KB n = 199910
7 Correct 187 ms 34284 KB n = 199999
8 Correct 188 ms 32472 KB n = 199997
9 Correct 234 ms 31880 KB n = 171294
10 Correct 198 ms 28472 KB n = 140872
11 Correct 207 ms 32516 KB n = 199886
12 Correct 205 ms 34416 KB n = 199996
13 Correct 203 ms 32984 KB n = 200000
14 Correct 216 ms 34228 KB n = 199998
15 Correct 207 ms 34016 KB n = 200000
16 Correct 252 ms 34668 KB n = 199998
17 Correct 206 ms 35188 KB n = 200000
18 Correct 208 ms 34052 KB n = 190000
19 Correct 213 ms 32712 KB n = 177777
20 Correct 103 ms 17692 KB n = 100000
21 Correct 206 ms 35300 KB n = 200000
22 Correct 261 ms 35340 KB n = 200000
23 Correct 239 ms 35256 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 300 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 340 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 296 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 300 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 300 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 300 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 232 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 296 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 260 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 328 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 296 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 256 KB n = 16
49 Correct 210 ms 35260 KB n = 199999
50 Correct 236 ms 35216 KB n = 199991
51 Correct 252 ms 35184 KB n = 199993
52 Correct 159 ms 29572 KB n = 152076
53 Correct 94 ms 16948 KB n = 93249
54 Correct 193 ms 32340 KB n = 199910
55 Correct 187 ms 34284 KB n = 199999
56 Correct 188 ms 32472 KB n = 199997
57 Correct 234 ms 31880 KB n = 171294
58 Correct 198 ms 28472 KB n = 140872
59 Correct 207 ms 32516 KB n = 199886
60 Correct 205 ms 34416 KB n = 199996
61 Correct 203 ms 32984 KB n = 200000
62 Correct 216 ms 34228 KB n = 199998
63 Correct 207 ms 34016 KB n = 200000
64 Correct 252 ms 34668 KB n = 199998
65 Correct 206 ms 35188 KB n = 200000
66 Correct 208 ms 34052 KB n = 190000
67 Correct 213 ms 32712 KB n = 177777
68 Correct 103 ms 17692 KB n = 100000
69 Correct 206 ms 35300 KB n = 200000
70 Correct 261 ms 35340 KB n = 200000
71 Correct 239 ms 35256 KB n = 200000
72 Correct 229 ms 35284 KB n = 200000
73 Correct 204 ms 35272 KB n = 200000
74 Correct 214 ms 35216 KB n = 200000
75 Correct 201 ms 35196 KB n = 200000
76 Correct 213 ms 35216 KB n = 200000
77 Correct 175 ms 25448 KB n = 200000
78 Correct 161 ms 25464 KB n = 200000
79 Correct 187 ms 33256 KB n = 184307
80 Correct 74 ms 15024 KB n = 76040
81 Correct 199 ms 32612 KB n = 199981
82 Correct 202 ms 34560 KB n = 199994
83 Correct 204 ms 32988 KB n = 199996
84 Correct 212 ms 34264 KB n = 199998
85 Correct 268 ms 34024 KB n = 200000
86 Correct 234 ms 34788 KB n = 199998
87 Correct 201 ms 35296 KB n = 200000
88 Correct 229 ms 35196 KB n = 200000
89 Correct 210 ms 35180 KB n = 200000
90 Correct 230 ms 35220 KB n = 200000
91 Correct 226 ms 35212 KB n = 200000
92 Correct 244 ms 35216 KB n = 200000