Submission #1171876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171876		boss_zz	Amusement Park (JOI17_amusement_park)	C++20	80 / 100	15 ms	2120 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MX=1e4+5,inf=1e18;
namespace J{
    ll n,m,dsu[MX],dfn[MX],timer,sz[MX],ans;
    vector<vector<ll> > adj(MX);
    void init(){
        iota(dsu,dsu+n,0);
    }
    ll findsu(ll x){
        if(dsu[x]==x) return x;
        return dsu[x]=findsu(dsu[x]);
    }
    void combine(ll a,ll b){
        a=findsu(a);
        b=findsu(b);
        if(a==b) return ;
        dsu[b]=a;
    }
    void dfs(ll v,ll lst){
        dfn[v]=timer++;
        timer%=60;
        sz[v]=1;
        for(ll cur:adj[v]){
            if(cur==lst) continue;
            dfs(cur,v);
            sz[v]+=sz[cur];
        }
    }
}
void Joi(int N, int M, int A[], int B[], long long X, int T){
    J::n=N;J::m=M;
    J::init();
    rep(i,0,J::m-1){
        ll u=A[i],v=B[i];
        if(J::findsu(u)!=J::findsu(v)){
            J::adj[u].push_back(v);
            J::adj[v].push_back(u);
            J::combine(u,v);
        }
    }
    J::dfs(0,-1);
    rep(i,0,J::n-1) MessageBoard(i,(X>>J::dfn[i])&1LL);
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
namespace I{
    const ll MX=1e4+5,inf=1e18;
    ll n,m,dsu[MX],dfn[MX],timer,sz[MX],ans,par[MX];
    vector<vector<ll> > adj(MX);
    bitset<70> flag;
    void init(){
        iota(dsu+1,dsu+n+1,1);
    }
    ll findsu(ll x){
        if(dsu[x]==x) return x;
        return dsu[x]=findsu(dsu[x]);
    }
    void combine(ll a,ll b){
        a=findsu(a);
        b=findsu(b);
        if(a==b) return ;
        dsu[b]=a;
    }
    void dfs(ll v,ll lst){
        dfn[v]=timer++;
        timer%=60;
        sz[v]=1;
        for(ll cur:adj[v]){
            if(cur==lst) continue;
            par[cur]=v;
            dfs(cur,v);
            sz[v]+=sz[cur];
        }
    }
    bool check(){
        rep(i,0,59) if(!flag[i]) return false;
        return true;
    }
    void upd(ll v,ll x){
        //cout<<v<<' '<<x<<' '<<dfn[v]<<'\n';
        flag[dfn[v]]=1;
        if(x) ans|=(1LL<<dfn[v]);
    }
    void DFS(ll v,ll lst){
        if(check()) return ;
        for(ll cur:adj[v]){
            if(cur==lst) continue;
            upd(cur,Move(cur));
            DFS(cur,v);
            if(check()) return ;
            upd(v,Move(v));
            if(check()) return ;
        }
    }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    I::n=N;I::m=M;
    I::init();
    rep(i,0,I::m-1){
        ll u=A[i],v=B[i];
        if(I::findsu(u)!=I::findsu(v)){
            I::adj[u].push_back(v);
            I::adj[v].push_back(u);
            I::combine(u,v);
        }
    }
    I::par[0]=-1;
    I::dfs(0,-1);
    I::upd(P,V);
    while(I::sz[P]<60&&I::par[P]!=-1){
        I::upd(I::par[P],Move(I::par[P]));
        P=I::par[P];
        if(I::check()) return I::ans;
    } 
    I::DFS(P,I::par[P]);
    //cout<<I::ans<<'\n';
    return I::ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 52 / 55
• Subtask 5: 0 / 17