Submission #1212079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212079		boss_zz	Amusement Park (JOI17_amusement_park)	C++20	80 / 100	14 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;
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){
    n=N;m=M;
    init();
    rep(i,0,m-1){
        ll u=A[i],v=B[i];
        if(findsu(u)!=findsu(v)){
            adj[u].push_back(v);
            adj[v].push_back(u);
            combine(u,v);
        }
    }
    dfs(0,-1);
    rep(i,0,n-1) MessageBoard(i,(X>>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;
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){
    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) {
    n=N;m=M;
    init();
    rep(i,0,m-1){
        ll u=A[i],v=B[i];
        if(findsu(u)!=findsu(v)){
            adj[u].push_back(v);
            adj[v].push_back(u);
            combine(u,v);
        }
    }
    par[0]=-1;
    dfs(0,-1);
    upd(P,V);
    while(sz[P]<60&&par[P]!=-1){
        upd(par[P],Move(par[P]));
        P=par[P];
        if(check()) return ans;
    } 
    DFS(P,par[P]);
    return ans;
}

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