oj.uz

Submission #373918

# Submission time Handle Problem Language Result Execution time Memory
373918 2021-03-06T05:56:57 Z rrrr10000 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 290 ms 64256 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
#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 lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
#include "Joi.h"
void Joi(int n,int m,int a[],int b[],ll res,int t){
    vi dep(n);
    vvi G(n);
    vb done(n,false);
    vi id(n,-1);
    rep(i,m){
        G[a[i]].pb(b[i]);
        G[b[i]].pb(a[i]);
    }
    vvi g(n);vi par(n,-1);
    ll cnt=0;
    vb sp(n,false);set<ll> S;
    function<void(ll)> dfs=[&](ll i){
        if(cnt<60){
            id[i]=cnt;
            sp[i]=true;
            S.insert(i);
            cnt++;
        }
        done[i]=true;
        for(ll x:G[i])if(!done[x]){
            g[i].pb(x);par[x]=i;dfs(x);
        }
    };dfs(0);
    vector<set<ll>> memo(n);
    rep(i,n)if(sp[i])memo[i]=S;
    function<void(ll)> dfs2=[&](ll i){
        int prev=-1;
        if(id[i]==-1){
            S.insert(i);
            sp[i]=true;
            auto itr=S.begin();
            while(true){
                assert(itr!=S.end());
                if(*itr==i){
                    itr++;continue;
                }
                ll jisuu=0;
                if(par[*itr]!=-1&&sp[par[*itr]])jisuu++;
                for(ll x:g[*itr]){
                    if(sp[x])jisuu++;
                    if(jisuu>1)break;
                }
                assert(jisuu);
                if(jisuu==1){
                    id[i]=id[*itr];
                    prev=*itr;
                    sp[*itr]=false;
                    S.erase(itr);
                    break;
                }
                itr++;
            }
            memo[i]=S;
        }
        for(ll x:g[i])dfs2(x);
        if(prev!=-1){
            sp[i]=false;
            S.erase(i);
            S.insert(prev);
            sp[prev]=true;
        }
    };dfs2(0);
    rep(i,n){
        set<ll> U;
        auto itr=memo[i].begin();
        assert(memo[i].size()==60);
        rep(i,60){
            U.insert(id[*itr]);
            itr++;
        }
        assert(U.size()==60);
    }
    // outv(id);
    rep(i,n)MessageBoard(i,res>>id[i]&1);
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
#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 lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
#include "Ioi.h"
ll Ioi(int n,int m,int a[],int b[],int p,int v,int t){
    vi dep(n);
    vvi G(n);
    vb done(n,false);
    vi id(n,-1);
    rep(i,m){
        G[a[i]].pb(b[i]);
        G[b[i]].pb(a[i]);
    }
    vvi g(n);vi par(n,-1);
    ll cnt=0;
    vb sp(n,false);set<ll> S;
    function<void(ll)> dfs=[&](ll i){
        if(cnt<60){
            id[i]=cnt;
            sp[i]=true;
            S.insert(i);
            cnt++;
        }
        done[i]=true;
        for(ll x:G[i])if(!done[x]){
            g[i].pb(x);par[x]=i;dfs(x);
        }
    };dfs(0);
    vector<set<ll>> memo(n);
    rep(i,n)if(sp[i])memo[i]=S;
    function<void(ll)> dfs2=[&](ll i){
        int prev=-1;
        if(id[i]==-1){
            S.insert(i);
            sp[i]=true;
            auto itr=S.begin();
            while(true){
                assert(itr!=S.end());
                if(*itr==i){
                    itr++;continue;
                }
                ll jisuu=0;
                if(par[*itr]!=-1&&sp[par[*itr]])jisuu++;
                for(ll x:g[*itr]){
                    if(sp[x])jisuu++;
                    if(jisuu>1)break;
                }
                assert(jisuu);
                if(jisuu==1){
                    id[i]=id[*itr];
                    prev=*itr;
                    sp[*itr]=false;
                    S.erase(itr);
                    break;
                }
                itr++;
            }
            memo[i]=S;
        }
        for(ll x:g[i])dfs2(x);
        if(prev!=-1){
            sp[i]=false;
            S.erase(i);
            S.insert(prev);
            sp[prev]=true;
        }
    };dfs2(0);
    vb use(n,false);vi num(n);
    auto itr=memo[p].begin();
    rep(i,60){
        use[*itr]=true;
        itr++;
    }
    num[p]=v;
    REP(i,1,n)g[i].pb(par[i]);
    function<void(ll,ll)> slv=[&](ll i,ll prv){
        for(ll x:g[i])if(x!=prv&&use[x]){
            num[x]=Move(x);
            slv(x,i);
            Move(i);
        }
    };slv(p,-1);
    ll ans=0;
    rep(i,n)if(use[i])ans+=num[i]<<id[i];
    return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1560 KB Output is correct
2 Correct 3 ms 1640 KB Output is correct
3 Correct 7 ms 2672 KB Output is correct
4 Correct 3 ms 1264 KB Output is correct
5 Correct 4 ms 1404 KB Output is correct
6 Correct 3 ms 1896 KB Output is correct
7 Correct 8 ms 2672 KB Output is correct
8 Correct 5 ms 2796 KB Output is correct
9 Correct 6 ms 2288 KB Output is correct
10 Correct 3 ms 1640 KB Output is correct
11 Correct 7 ms 2180 KB Output is correct
12 Correct 2 ms 1128 KB Output is correct
13 Correct 6 ms 2760 KB Output is correct
14 Correct 7 ms 2672 KB Output is correct
15 Correct 7 ms 2932 KB Output is correct
16 Correct 6 ms 2672 KB Output is correct
17 Correct 8 ms 2764 KB Output is correct
18 Correct 6 ms 2588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 64232 KB Output is correct
2 Correct 276 ms 64212 KB Output is correct
3 Correct 276 ms 64004 KB Output is correct
4 Correct 254 ms 61728 KB Output is correct
5 Correct 269 ms 62792 KB Output is correct
6 Correct 258 ms 62440 KB Output is correct
7 Correct 263 ms 62408 KB Output is correct
8 Correct 262 ms 62708 KB Output is correct
9 Correct 257 ms 62620 KB Output is correct
10 Correct 199 ms 61840 KB Output is correct
11 Correct 196 ms 61880 KB Output is correct
12 Correct 221 ms 56068 KB Output is correct
13 Correct 216 ms 56248 KB Output is correct
14 Correct 227 ms 59028 KB Output is correct
15 Correct 228 ms 61604 KB Output is correct
16 Correct 232 ms 61764 KB Output is correct
17 Correct 230 ms 61844 KB Output is correct
18 Correct 237 ms 61944 KB Output is correct
19 Correct 234 ms 61596 KB Output is correct
20 Correct 186 ms 62748 KB Output is correct
21 Correct 184 ms 62028 KB Output is correct
22 Correct 272 ms 62408 KB Output is correct
23 Correct 262 ms 62620 KB Output is correct
24 Correct 262 ms 62492 KB Output is correct
25 Correct 266 ms 62696 KB Output is correct
26 Correct 256 ms 62620 KB Output is correct
27 Correct 263 ms 62916 KB Output is correct
28 Correct 290 ms 63328 KB Output is correct
29 Correct 249 ms 57112 KB Output is correct
30 Correct 249 ms 59732 KB Output is correct
31 Correct 4 ms 1668 KB Output is correct
32 Correct 4 ms 1896 KB Output is correct
33 Correct 8 ms 2672 KB Output is correct
34 Correct 3 ms 1640 KB Output is correct
35 Correct 3 ms 1440 KB Output is correct
36 Correct 2 ms 1256 KB Output is correct
37 Correct 2 ms 1276 KB Output is correct
38 Correct 2 ms 1128 KB Output is correct
39 Correct 2 ms 1128 KB Output is correct
40 Correct 3 ms 1504 KB Output is correct
41 Correct 3 ms 1408 KB Output is correct
42 Correct 2 ms 1128 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1384 KB Output is correct
2 Correct 4 ms 1436 KB Output is correct
3 Correct 3 ms 1384 KB Output is correct
4 Correct 32 ms 11044 KB Output is correct
5 Correct 30 ms 11128 KB Output is correct
6 Correct 30 ms 11044 KB Output is correct
7 Correct 33 ms 11064 KB Output is correct
8 Correct 36 ms 10916 KB Output is correct
9 Correct 183 ms 63220 KB Output is correct
10 Correct 186 ms 63220 KB Output is correct
11 Correct 184 ms 63344 KB Output is correct
12 Correct 2 ms 1128 KB Output is correct
13 Correct 2 ms 1516 KB Output is correct
14 Correct 2 ms 1128 KB Output is correct
15 Correct 2 ms 1128 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 64256 KB Output is correct
2 Correct 285 ms 64220 KB Output is correct
3 Correct 266 ms 64176 KB Output is correct
4 Correct 240 ms 61988 KB Output is correct
5 Correct 262 ms 63280 KB Output is correct
6 Correct 257 ms 62660 KB Output is correct
7 Correct 271 ms 62652 KB Output is correct
8 Correct 257 ms 62236 KB Output is correct
9 Correct 261 ms 62500 KB Output is correct
10 Correct 204 ms 61676 KB Output is correct
11 Correct 196 ms 61728 KB Output is correct
12 Correct 214 ms 56428 KB Output is correct
13 Correct 218 ms 56068 KB Output is correct
14 Correct 231 ms 59100 KB Output is correct
15 Correct 228 ms 61632 KB Output is correct
16 Correct 227 ms 61852 KB Output is correct
17 Correct 236 ms 61724 KB Output is correct
18 Correct 247 ms 61972 KB Output is correct
19 Correct 239 ms 61596 KB Output is correct
20 Correct 184 ms 62960 KB Output is correct
21 Correct 194 ms 62200 KB Output is correct
22 Correct 261 ms 62760 KB Output is correct
23 Correct 263 ms 62772 KB Output is correct
24 Correct 274 ms 62492 KB Output is correct
25 Correct 271 ms 62892 KB Output is correct
26 Correct 282 ms 62864 KB Output is correct
27 Correct 269 ms 62888 KB Output is correct
28 Correct 271 ms 62676 KB Output is correct
29 Correct 231 ms 56992 KB Output is correct
30 Correct 244 ms 59408 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 64224 KB Output is correct
2 Correct 277 ms 64160 KB Output is correct
3 Correct 275 ms 64004 KB Output is correct
4 Correct 231 ms 61596 KB Output is correct
5 Correct 256 ms 63516 KB Output is correct
6 Correct 258 ms 62468 KB Output is correct
7 Correct 263 ms 62352 KB Output is correct
8 Correct 260 ms 62752 KB Output is correct
9 Correct 260 ms 62628 KB Output is correct
10 Correct 192 ms 61696 KB Output is correct
11 Correct 194 ms 61736 KB Output is correct
12 Correct 220 ms 56428 KB Output is correct
13 Correct 213 ms 56068 KB Output is correct
14 Correct 235 ms 59068 KB Output is correct
15 Correct 234 ms 61596 KB Output is correct
16 Correct 231 ms 61596 KB Output is correct
17 Correct 232 ms 61788 KB Output is correct
18 Correct 238 ms 61696 KB Output is correct
19 Correct 235 ms 61596 KB Output is correct
20 Correct 182 ms 62748 KB Output is correct
21 Correct 186 ms 62056 KB Output is correct
22 Correct 263 ms 62364 KB Output is correct
23 Correct 259 ms 62364 KB Output is correct
24 Correct 257 ms 62668 KB Output is correct
25 Correct 263 ms 62364 KB Output is correct
26 Correct 270 ms 62236 KB Output is correct
27 Correct 257 ms 62880 KB Output is correct
28 Correct 259 ms 63252 KB Output is correct
29 Correct 239 ms 57220 KB Output is correct
30 Correct 248 ms 59624 KB Output is correct
31 Correct 4 ms 1668 KB Output is correct
32 Correct 5 ms 1768 KB Output is correct
33 Correct 6 ms 2588 KB Output is correct
34 Correct 3 ms 1880 KB Output is correct
35 Correct 3 ms 1256 KB Output is correct
36 Correct 3 ms 1256 KB Output is correct
37 Correct 2 ms 1276 KB Output is correct
38 Correct 2 ms 1128 KB Output is correct
39 Correct 2 ms 1128 KB Output is correct
40 Correct 3 ms 1384 KB Output is correct
41 Correct 3 ms 1384 KB Output is correct
42 Correct 2 ms 1256 KB Output is correct