Submission #1155250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155250		KhoaDuy	Amusement Park (JOI17_amusement_park)	C++20	28 / 100	13 ms	1864 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000;
int dsu[MAXN];
int in[MAXN];
int tim=0;
vector<vector<int>> graph;
int pa[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){
    pa[u]=p;
    in[u]=tim;
    tim++;
    for(int v:graph[u]){
        if(v!=p){
            setup(v,u);
        }
    }
}
void buildtree(int a[],int b[],int n,int m){
    graph.clear();
    graph.resize(n);
    tim=0;
    for(int i=0;i<n;i++){
        dsu[i]=-1,in[i]=0,pa[i]=0;
    }
    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);
}
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<<(in[i]%60))){
            MessageBoard(i,1);
        }
        else{
            MessageBoard(i,0);
        }
    }
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000;
int dsu[MAXN];
int in[MAXN];
int tim=0;
vector<vector<int>> graph;
int pa[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){
    pa[u]=p;
    in[u]=tim;
    tim++;
    for(int v:graph[u]){
        if(v!=p){
            setup(v,u);
        }
    }
}
void buildtree(int a[],int b[],int n,int m){
    graph.clear();
    graph.resize(n);
    tim=0;
    for(int i=0;i<n;i++){
        dsu[i]=-1,in[i]=0,pa[i]=0;
    }
    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);
}
long long x=-1;
int val[60];
int wri[MAXN];
void update(int k,int bit){
    val[k]=bit;
    bool flag=true;
    for(int i=0;i<60;i++){
        if(val[i]==-1){
            flag=false;
            break;
        }
    }
    if(flag){
        x=0;
        for(int i=0;i<60;i++){
            if(val[i]){
                x^=(1LL<<i);
            }
        }
    }
}
void DFS(int u,int p,char dir){
    update(in[u]%60,wri[u]);
    if(x!=-1){
        return;
    }
    if(dir=='R'){
        for(int i=(int)graph[u].size()-1;i>=0;i--){
            int v=graph[u][i];
            if(v!=p){
                wri[v]=Move(v);
                DFS(v,u,dir);
                if(x!=-1){
                    return;
                }
                wri[u]=Move(u);
            }
        }
    }
    else{
        for(int v:graph[u]){
            if(v!=p){
                wri[v]=Move(v);
                DFS(v,u,dir);
                if(x!=-1){
                    return;
                }
                wri[u]=Move(u);
            }
        }
    }
}
long long Ioi(int n,int m,int a[],int b[],int u,int V,int t){
    memset(val,-1,sizeof(val));
    buildtree(a,b,n,m);
    wri[u]=V;
    int last=-1;
    while(x==-1&&u!=-1){
        update(in[u]%60,wri[u]);
        if(x!=-1){
            return x;
        }
        int pos=-1;
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i];
            if(v!=pa[u]&&v==last){
                pos=i;
                break;
            }
        }
        for(int i=pos-1;i>=0;i--){
            int v=graph[u][i];
            if(v!=pa[u]){
                wri[v]=Move(v);
                DFS(v,u,'R');
                if(x!=-1){
                    return x;
                }
                wri[u]=Move(u);
            }
        }
        for(int i=pos+1;i<graph[u].size();i++){
            int v=graph[u][i];
            if(v!=pa[u]){
                wri[v]=Move(v);
                DFS(v,u,'L');
                if(x!=-1){
                    return x;
                }
                wri[u]=Move(u);
            }
        }
        last=u;
        u=pa[u];
        if(u!=-1){
            wri[u]=Move(u);
        }
    }
    return x;
}

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