Submission #373918

#	Time	Username	Problem	Language	Result	Execution time	Memory
373918		rrrr10000	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	290 ms	64256 KiB

Joi

#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);
}

Ioi

#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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17