Submission #1285279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285279		trandangquang	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	119 ms	16396 KiB

Joi

#include"Joi.h"
#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<


namespace joi{
    const int MAX = 10005;

    int n,m,id[MAX],deg[MAX]; /// id: chua dinh nao
    bitset<MAX> isEdge[MAX];
    vector<int> adj[MAX];
    array<int,60> st[MAX];

    int par[MAX];
    int find(int a){
        return par[a]==0?a:par[a]=find(par[a]);
    }
    bool unite(int a, int b){
        a=find(a); b=find(b);
        if(a==b)return false;
        par[b]=a;
        return true;
    }

    bool vis[MAX]; /// init verteces
    void build_first(){
        array<int,60> arr; int cnt=0;
        queue<int> q; q.push(0); vis[0]=1; id[0]=cnt; arr[cnt++]=0;

        while(q.size()){
            int u=q.front(); q.pop();
            for(int v:adj[u]) if(!vis[v]){
                if(cnt==60) break;
                q.push(v); vis[v]=1; id[v]=cnt; arr[cnt++]=v;
            }
        }

        assert(cnt==60);
        rep(i,cnt) st[arr[i]]=arr;
    }

    void extend(){
        queue<int> q;
        rep(i,n) if(vis[i]) q.push(i);

        while(q.size()){
            int u=q.front(); q.pop();

            int d1=-1;
            foru(i,0,59) foru(j,i+1,59){
                if(isEdge[st[u][i]][st[u][j]]){
                    ++deg[st[u][i]]; ++deg[st[u][j]];
                }
            }
            rep(i,60) if(st[u][i]!=u && deg[st[u][i]]==1){
                d1=i; break;
            }
            foru(i,0,59) foru(j,i+1,59){
                if(isEdge[st[u][i]][st[u][j]]){
                    --deg[st[u][i]]; --deg[st[u][j]];
                }
            }
            assert(d1!=-1);

            for(int v:adj[u]) if(!vis[v]){
                st[v]=st[u];
                id[v]=id[st[v][d1]];
                st[v][d1]=v;

                q.push(v); vis[v]=1;
            }
        }
    }

    void Joi(int N, int M, int A[], int B[], long long X, int T) {
        /// build lai canh
        n=N, m=M;
        rep(i,m){
            if(unite(A[i],B[i])){
                isEdge[A[i]][B[i]]=1;
                isEdge[B[i]][A[i]]=1;
                adj[A[i]].eb(B[i]);
                adj[B[i]].eb(A[i]);
            }
        }
        build_first();
        extend();
        rep(i,N) MessageBoard(i,X>>id[i]&1);
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    joi::Joi(N,M,A,B,X,T);
}

Ioi

#include"Ioi.h"
#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<


namespace ioi{
    const int MAX=10005;

    int n,m,id[MAX],deg[MAX]; /// id: chua dinh nao
    bitset<MAX> isEdge[MAX];
    vector<int> adj[MAX];
    array<int,60> st[MAX];

    int par[MAX];
    int find(int a){
        return par[a]==0?a:par[a]=find(par[a]);
    }
    bool unite(int a, int b){
        a=find(a); b=find(b);
        if(a==b)return false;
        par[b]=a;
        return true;
    }

    bool vis[MAX]; /// init verteces
    void build_first(){
        array<int,60> arr; int cnt=0;
        queue<int> q; q.push(0); vis[0]=1; id[0]=cnt; arr[cnt++]=0;

        while(q.size()){
            int u=q.front(); q.pop();
            for(int v:adj[u]) if(!vis[v]){
                if(cnt==60) break;
                q.push(v); vis[v]=1; id[v]=cnt; arr[cnt++]=v;
            }
        }

        assert(cnt==60);
        rep(i,cnt) st[arr[i]]=arr;
    }

    void extend(){
        queue<int> q;
        rep(i,n) if(vis[i]) q.push(i);

        while(q.size()){
            int u=q.front(); q.pop();

            int d1=-1;
            foru(i,0,59) foru(j,i+1,59){
                if(isEdge[st[u][i]][st[u][j]]){
                    ++deg[st[u][i]]; ++deg[st[u][j]];
                }
            }
            rep(i,60) if(st[u][i]!=u && deg[st[u][i]]==1){
                d1=i; break;
            }
            foru(i,0,59) foru(j,i+1,59){
                if(isEdge[st[u][i]][st[u][j]]){
                    --deg[st[u][i]]; --deg[st[u][j]];
                }
            }
            assert(d1!=-1);

            for(int v:adj[u]) if(!vis[v]){
                st[v]=st[u];
                id[v]=id[st[v][d1]];
                st[v][d1]=v;

                q.push(v); vis[v]=1;
            }
        }
    }

    int res[60]; bool inP[MAX];
    void dfsAnswer(int u, int p=-1){
        for(int v:adj[u]) if(inP[v] && v!=p){
            res[id[v]]=Move(v);
            dfsAnswer(v,u);
            Move(u);
        }
    }
    long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
        /// build lai canh
        n=N, m=M;
        rep(i,m){
            if(unite(A[i],B[i])){
                isEdge[A[i]][B[i]]=1;
                isEdge[B[i]][A[i]]=1;
                adj[A[i]].eb(B[i]);
                adj[B[i]].eb(A[i]);
            }
        }
        build_first();
        extend();
        res[id[P]]=V;
        rep(i,60) inP[st[P][i]]=1;
        dfsAnswer(P);

        ll x=0;
        rep(i,60) if(res[i]) x|=(1LL<<i);
        return x;
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
    return ioi::Ioi(N,M,A,B,P,V,T);
}

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