Submission #78377

#	Time	Username	Problem	Language	Result	Execution time	Memory
78377		nxteru	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	12 ms	2492 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
int nj,mj[60],parj[10005],wj[10005],kj,sj[60],oj[60],paj;
ll anj[60];
bool ej[60][60];
vector<int>gj[10005];
int findj(int x){
    if(x==parj[x])return x;
    return parj[x]=findj(parj[x]);
}
bool samej(int x,int y){return findj(x)==findj(y);}
void unitj(int x,int y){parj[findj(x)]=findj(y);}
void dfs1j(int v,int p){
    oj[kj]=v;
    wj[v]=kj++;
    if(p!=-1){
        ej[wj[v]][wj[p]]=true;
        ej[wj[p]][wj[v]]=true;
        sj[wj[v]]++;
        sj[wj[p]]++;
    }
    if(kj==60)return;
    for(int i=0;i<gj[v].size();i++){
        int u=gj[v][i];
        if(u!=p)dfs1j(u,v);
    }
}
void dfs2j(int v,int l,int p,int o[60],bool e[60][60],int s[60]){
    if(wj[v]!=-1){
        for(int i=0;i<gj[v].size();i++){
            int u=gj[v][i];
            if(u!=p){
                dfs2j(u,wj[v],v,o,e,s);
            }
        }
        return;
    }
    int r;
    for(int i=0;i<60;i++){
        if(s[i]==1&&o[i]!=p){
            r=i;
            break;
        }
    }
    for(int i=0;i<60;i++){
        e[r][i]=false;
        e[i][r]=false;
    }
    wj[v]=r;
    o[r]=v;
    e[r][l]=true;
    e[l][r]=true;
    s[l]++;
    for(int i=0;i<gj[v].size();i++){
        int u=gj[v][i];
        if(u!=p){
            dfs2j(u,wj[v],v,o,e,s);
        }
    }
}
void Joi(int N,int M,int A[],int B[],ll X,int t){
    nj=N;
    for(int i=0;i<nj;i++){
        parj[i]=i;
        wj[i]=-1;
    }
    for(int i=0;i<M;i++){
        if(!samej(A[i],B[i])){
            gj[A[i]].PB(B[i]);
            gj[B[i]].PB(A[i]);
            unitj(A[i],B[i]);
        }
    }
    for(int i=0;i<60;i++)mj[i]=(X>>i)&1;
    dfs1j(0,-1);
    dfs2j(0,wj[0],-1,oj,ej,sj);
    for(int i=0;i<nj;i++){
        MessageBoard(i,mj[wj[i]]); 
    }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
int n,m[60],par[10005],w[10005],k,S[60],O[60],PA;
ll an[60];
bool E[60][60];
vector<int>g[10005];
int find(int x){
    if(x==par[x])return x;
    return par[x]=find(par[x]);
}
bool same(int x,int y){return find(x)==find(y);}
void unit(int x,int y){par[find(x)]=find(y);}
void dfs1(int v,int p){
    O[k]=v;
    w[v]=k++;
    if(p!=-1){
        E[w[v]][w[p]]=true;
        E[w[p]][w[v]]=true;
        S[w[v]]++;
        S[w[p]]++;
    }
    if(k==60)return;
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p)dfs1(u,v);
    }
}
void dfs3(int v,int l,int p,int o[60],bool e[60][60],int s[60]){
    if(w[v]!=-1){
        for(int i=0;i<g[v].size();i++){
            int u=g[v][i];
            if(u!=p){
                dfs3(u,w[v],v,o,e,s);
            }
        }
        return;
    }
    int r;
    for(int i=0;i<60;i++){
        if(s[i]==1&&o[i]!=p){
            r=i;
            break;
        }
    }
    for(int i=0;i<60;i++){
        e[r][i]=false;
        e[i][r]=false;
    }
    w[v]=r;
    o[r]=v;
    e[r][l]=true;
    e[l][r]=true;
    s[l]++;
    if(v==PA){
        for(int i=0;i<60;i++){
            O[i]=o[i];
            for(int j=0;j<60;j++){
                E[i][j]=e[i][j];
            }
        }
        return;
    }
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p){
            dfs3(u,w[v],v,o,e,s);
        }
    }
}
void ans(int v,int p,int x){
    an[v]=x;
    for(int i=0;i<60;i++){
        if(E[v][i]&&i!=p){
            ans(i,v,Move(O[i]));
        }
    }
    if(p!=-1)Move(O[p]);
}
ll Ioi(int N,int M,int A[],int B[],int P,int X,int t){
    n=N;
    PA=P;
    for(int i=0;i<n;i++){
        par[i]=i;
        w[i]=-1;
    }
    for(int i=0;i<M;i++){
        if(!same(A[i],B[i])){
            g[A[i]].PB(B[i]);
            g[B[i]].PB(A[i]);
            unit(A[i],B[i]);
        }
    }
    dfs1(0,-1);
    if(w[P]==-1)dfs3(0,w[0],-1,O,E,S);
    ans(w[P],-1,X);
    ll res=0;
    for(ll i=0;i<60;i++)if(an[i]>0)res+=(1LL<<i);
    return res;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfs1j(int, int)':
Joi.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gj[v].size();i++){
                 ~^~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2j(int, int, int, int*, bool (*)[60], int*)':
Joi.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<gj[v].size();i++){
                     ~^~~~~~~~~~~~~
Joi.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gj[v].size();i++){
                 ~^~~~~~~~~~~~~
Joi.cpp:41:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int r;
         ^

Ioi.cpp: In function 'void dfs1(int, int)':
Ioi.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
Ioi.cpp: In function 'void dfs3(int, int, int, int*, bool (*)[60], int*)':
Ioi.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++){
                     ~^~~~~~~~~~~~
Ioi.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
Ioi.cpp:41:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int r;
         ^

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