Submission #78378

#	Time	Username	Problem	Language	Result	Execution time	Memory
78378		nxteru	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	11 ms	2600 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
static int n,m[60],par[10005],w[10005],k,S[60],O[60],PA;
static ll an[60];
static bool E[60][60];
static vector<int>g[10005];
static int find(int x){
    if(x==par[x])return x;
    return par[x]=find(par[x]);
}
static bool same(int x,int y){return find(x)==find(y);}
static void unit(int x,int y){par[find(x)]=find(y);}
static 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);
    }
}
static void dfs2(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){
                dfs2(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]++;
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p){
            dfs2(u,w[v],v,o,e,s);
        }
    }
}
void Joi(int N,int M,int A[],int B[],ll X,int t){
    n=N;
    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]);
        }
    }
    for(int i=0;i<60;i++)m[i]=(X>>i)&1;
    dfs1(0,-1);
    dfs2(0,w[0],-1,O,E,S);
    for(int i=0;i<n;i++){
        MessageBoard(i,m[w[i]]); 
    }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
static int n,m[60],par[10005],w[10005],k,S[60],O[60],PA;
static ll an[60];
static bool E[60][60];
static vector<int>g[10005];
static int find(int x){
    if(x==par[x])return x;
    return par[x]=find(par[x]);
}
static bool same(int x,int y){return find(x)==find(y);}
static void unit(int x,int y){par[find(x)]=find(y);}
static 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);
    }
}
static 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);
        }
    }
}
static 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 dfs1(int, int)':
Joi.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(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<g[v].size();i++){
                     ~^~~~~~~~~~~~
Joi.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
Joi.cpp: At global scope:
Joi.cpp:7:11: warning: 'an' defined but not used [-Wunused-variable]
 static ll an[60];
           ^~
Joi.cpp:6:54: warning: 'PA' defined but not used [-Wunused-variable]
 static int n,m[60],par[10005],w[10005],k,S[60],O[60],PA;
                                                      ^~
Joi.cpp: In function 'void dfs2(int, int, int, int*, bool (*)[60], int*)':
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: At global scope:
Ioi.cpp:6:14: warning: 'm' defined but not used [-Wunused-variable]
 static int n,m[60],par[10005],w[10005],k,S[60],O[60],PA;
              ^
Ioi.cpp: In function 'void dfs3(int, int, int, int*, bool (*)[60], int*)':
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