oj.uz

Submission #804608

# Submission time Handle Problem Language Result Execution time Memory
804608 2023-08-03T10:17:26 Z I_Love_EliskaM_ Roller Coaster Railroad (IOI16_railroad) C++14
64 / 100
 489 ms 50952 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second

struct DSU {
    vector<int> p,sz;
    DSU(int n) {
        forn(i,n) p.pb(i), sz.pb(1);
    }
    int get(int u) {
        return p[u]==u?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u),v=get(v);
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }
};

ll dp[1<<16][20];
bool foo(int a, int b) {
    return __builtin_popcount(a) < __builtin_popcount(b);
}
ll scuza(vector<int> s, vector<int> t) {

    int n=s.size();
    s.pb(-1); t.pb(0);
    vector<int> b;
    forn(i,1<<n) b.pb(i);
    sort(all(b),foo);
    forn(i,n+1) forn(j,1<<n) dp[j][i]=1e18;
    dp[0][n]=0;
    for(auto&m:b) {
        forn(i,n+1) {
            if (m) if (!(m&(1<<i))) continue;
            forn(j,n) {
                if (m&(1<<j)) continue;
                dp[m|(1<<j)][j]=min(dp[m|(1<<j)][j],dp[m][i] + max(t[i]-s[j],0));
            }
        }
    }
    ll ans=1e18;
    forn(i,n) ans=min(ans,dp[(1<<n)-1][i]);
    return ans;
 
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n=s.size();

    if (n<=16) return scuza(s,t);

    s.pb(1e9+7);
    t.pb(-1);
    ++n;

    int m=0;
    set<int> st; forn(i,n) st.insert(s[i]), st.insert(t[i]);
    map<int,int> c;
    for(auto&x:st) c[x]=m++;

    vector<int> pr(m);
    forn(i,n) s[i]=c[s[i]], t[i]=c[t[i]];

    DSU dsu(m);
    forn(i,n) {
        pr[t[i]]++;
        pr[s[i]]--;
        dsu.uni(s[i],t[i]);
    }
    for(int i=1; i<m; ++i) pr[i]+=pr[i-1];

    forn(i,m) {
        if (pr[i]<0) return 1;
        if (pr[i]>0) dsu.uni(i,i+1);
    }
    int ans=1;
    forn(i,n) ans&=dsu.get(i)==dsu.get(0);
    return !ans;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 47028 KB n = 199999
2 Correct 476 ms 47036 KB n = 199991
3 Correct 456 ms 50864 KB n = 199993
4 Correct 362 ms 38184 KB n = 152076
5 Correct 204 ms 24128 KB n = 93249
6 Correct 397 ms 42536 KB n = 199910
7 Correct 408 ms 49244 KB n = 199999
8 Correct 332 ms 42940 KB n = 199997
9 Correct 340 ms 42772 KB n = 171294
10 Correct 300 ms 36008 KB n = 140872
11 Correct 382 ms 43168 KB n = 199886
12 Correct 386 ms 49692 KB n = 199996
13 Correct 329 ms 44488 KB n = 200000
14 Correct 387 ms 49216 KB n = 199998
15 Correct 347 ms 48516 KB n = 200000
16 Correct 330 ms 50276 KB n = 199998
17 Correct 429 ms 50848 KB n = 200000
18 Correct 455 ms 47272 KB n = 190000
19 Correct 407 ms 44436 KB n = 177777
20 Correct 150 ms 25704 KB n = 100000
21 Correct 400 ms 50952 KB n = 200000
22 Correct 461 ms 50856 KB n = 200000
23 Correct 463 ms 50852 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 0 ms 340 KB n = 8
11 Correct 0 ms 340 KB n = 8
12 Correct 0 ms 340 KB n = 8
13 Correct 0 ms 340 KB n = 8
14 Correct 0 ms 340 KB n = 8
15 Correct 1 ms 340 KB n = 8
16 Correct 0 ms 340 KB n = 8
17 Correct 0 ms 340 KB n = 8
18 Correct 0 ms 340 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 0 ms 340 KB n = 8
22 Correct 1 ms 340 KB n = 8
23 Correct 0 ms 340 KB n = 8
24 Correct 1 ms 340 KB n = 8
25 Correct 1 ms 340 KB n = 8
26 Correct 0 ms 340 KB n = 8
27 Correct 0 ms 340 KB n = 8
28 Correct 0 ms 340 KB n = 8
29 Correct 43 ms 10832 KB n = 16
30 Correct 47 ms 10944 KB n = 16
31 Correct 44 ms 10832 KB n = 16
32 Correct 44 ms 10940 KB n = 16
33 Correct 44 ms 10940 KB n = 16
34 Correct 44 ms 10860 KB n = 16
35 Correct 44 ms 10832 KB n = 16
36 Correct 20 ms 5588 KB n = 15
37 Correct 0 ms 340 KB n = 8
38 Correct 45 ms 10956 KB n = 16
39 Correct 47 ms 10832 KB n = 16
40 Correct 1 ms 340 KB n = 9
41 Correct 43 ms 10944 KB n = 16
42 Correct 45 ms 10832 KB n = 16
43 Correct 48 ms 10832 KB n = 16
44 Correct 1 ms 340 KB n = 9
45 Correct 23 ms 5588 KB n = 15
46 Correct 55 ms 10832 KB n = 16
47 Correct 44 ms 10832 KB n = 16
48 Correct 44 ms 10944 KB n = 16
49 Correct 474 ms 47028 KB n = 199999
50 Correct 476 ms 47036 KB n = 199991
51 Correct 456 ms 50864 KB n = 199993
52 Correct 362 ms 38184 KB n = 152076
53 Correct 204 ms 24128 KB n = 93249
54 Correct 397 ms 42536 KB n = 199910
55 Correct 408 ms 49244 KB n = 199999
56 Correct 332 ms 42940 KB n = 199997
57 Correct 340 ms 42772 KB n = 171294
58 Correct 300 ms 36008 KB n = 140872
59 Correct 382 ms 43168 KB n = 199886
60 Correct 386 ms 49692 KB n = 199996
61 Correct 329 ms 44488 KB n = 200000
62 Correct 387 ms 49216 KB n = 199998
63 Correct 347 ms 48516 KB n = 200000
64 Correct 330 ms 50276 KB n = 199998
65 Correct 429 ms 50848 KB n = 200000
66 Correct 455 ms 47272 KB n = 190000
67 Correct 407 ms 44436 KB n = 177777
68 Correct 150 ms 25704 KB n = 100000
69 Correct 400 ms 50952 KB n = 200000
70 Correct 461 ms 50856 KB n = 200000
71 Correct 463 ms 50852 KB n = 200000
72 Correct 489 ms 50924 KB n = 200000
73 Incorrect 423 ms 50856 KB answer is not correct: 1 instead of 34382661743
74 Halted 0 ms 0 KB -