Submission #1155283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155283		KhoaDuy	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	32 ms	5192 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000;
const int MAXBIT=60;
int dsu[MAXN];
vector<vector<int>> graph;
vector<vector<int>> comp;
int num[MAXN];
bool in[MAXN];
int Findset(int i){
    if(dsu[i]<0){
        return i;
    }
    int root=Findset(dsu[i]);
    dsu[i]=root;
    return root;
}
void unite(int u,int v){
    u=Findset(u),v=Findset(v);
    if(u==v){
        return;
    }
    if(dsu[u]<dsu[v]){
        swap(u,v);
    }
    dsu[v]+=dsu[u];
    dsu[u]=v;
}
void setup(int u,int p){
    comp[0].push_back(u);
    if(comp[0].size()==MAXBIT){
        return;
    }
    for(int v:graph[u]){
        if(v!=p){
            setup(v,u);
            if(comp[0].size()==MAXBIT){
                return;
            }
        }
    }
}
int getleaf(int u,int p){
    for(int v:graph[u]){
        if(v!=p&&in[v]){
            return getleaf(v,u);
        }
    }
    return u;
}
void DFS(int u,int p){
    if(num[u]==-1){
        assert(p!=-1);
        for(int v:comp[p]){
            in[v]=true;
        }
        int w=getleaf(p,-1);
        num[u]=num[w];
        comp[u].push_back(u);
        for(int v:comp[p]){
            in[v]=false;
            if(v!=w){
                comp[u].push_back(v);
            }
        }
    }
    for(int v:graph[u]){
        if(v!=p){
            DFS(v,u);
        }
    }
}
void buildtree(int a[],int b[],int n,int m){
    graph.clear();
    graph.resize(n);
    comp.clear();
    comp.resize(n);
    for(int i=0;i<n;i++){
        dsu[i]=-1;
        num[i]=-1;
        in[i]=false;
    }
    for(int i=0;i<m;i++){
        if(Findset(a[i])!=Findset(b[i])){
            unite(a[i],b[i]);
            graph[a[i]].push_back(b[i]);
            graph[b[i]].push_back(a[i]);
        }
    }
    setup(0,-1);
    for(int i=0;i<comp[0].size();i++){
        num[comp[0][i]]=i;
    }
    for(int u:comp[0]){
        if(u!=0){
            for(int v:comp[0]){
                comp[u].push_back(v);
            }
        }
    }
    DFS(0,-1);
}
void Joi(int n,int m,int a[],int b[],long long x,int t){
    buildtree(a,b,n,m);
    for(int i=0;i<n;i++){
        if(x&(1LL<<(num[i]))){
            MessageBoard(i,1);
        }
        else{
            MessageBoard(i,0);
        }
    }
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000;
const int MAXBIT=60;
int dsu[MAXN];
vector<vector<int>> graph;
vector<vector<int>> comp;
int num[MAXN];
bool in[MAXN];
int Findset(int i){
    if(dsu[i]<0){
        return i;
    }
    int root=Findset(dsu[i]);
    dsu[i]=root;
    return root;
}
void unite(int u,int v){
    u=Findset(u),v=Findset(v);
    if(u==v){
        return;
    }
    if(dsu[u]<dsu[v]){
        swap(u,v);
    }
    dsu[v]+=dsu[u];
    dsu[u]=v;
}
void setup(int u,int p){
    comp[0].push_back(u);
    if(comp[0].size()==MAXBIT){
        return;
    }
    for(int v:graph[u]){
        if(v!=p){
            setup(v,u);
            if(comp[0].size()==MAXBIT){
                return;
            }
        }
    }
}
int getleaf(int u,int p){
    for(int v:graph[u]){
        if(v!=p&&in[v]){
            return getleaf(v,u);
        }
    }
    return u;
}
void DFS(int u,int p){
    if(num[u]==-1){
        assert(p!=-1);
        for(int v:comp[p]){
            in[v]=true;
        }
        int w=getleaf(p,-1);
        num[u]=num[w];
        comp[u].push_back(u);
        for(int v:comp[p]){
            in[v]=false;
            if(v!=w){
                comp[u].push_back(v);
            }
        }
    }
    for(int v:graph[u]){
        if(v!=p){
            DFS(v,u);
        }
    }
}
void buildtree(int a[],int b[],int n,int m){
    graph.clear();
    graph.resize(n);
    comp.clear();
    comp.resize(n);
    for(int i=0;i<n;i++){
        dsu[i]=-1;
        num[i]=-1;
        in[i]=false;
    }
    for(int i=0;i<m;i++){
        if(Findset(a[i])!=Findset(b[i])){
            unite(a[i],b[i]);
            graph[a[i]].push_back(b[i]);
            graph[b[i]].push_back(a[i]);
        }
    }
    setup(0,-1);
    for(int i=0;i<comp[0].size();i++){
        num[comp[0][i]]=i;
    }
    for(int u:comp[0]){
        if(u!=0){
            for(int v:comp[0]){
                comp[u].push_back(v);
            }
        }
    }
    DFS(0,-1);
}
long long x=0;
int val[MAXN];
void calc(int u,int p){
    if(val[u]==1){
        x^=(1LL<<num[u]);
    }
    for(int v:graph[u]){
        if(v!=p&&in[v]){
            val[v]=Move(v);
            calc(v,u);
            val[u]=Move(u);
        }
    }
}
long long Ioi(int n,int m,int a[],int b[],int u,int V,int t){
    buildtree(a,b,n,m);
    for(int v:comp[u]){
        in[v]=true;
    }
    val[u]=V;
    calc(u,-1);
    return x;
}

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