oj.uz

Submission #78371

# Submission time Handle Problem Language Result Execution time Memory
78371 2018-10-04T12:50:06 Z nxteru Amusement Park (JOI17_amusement_park) C++14
0 / 100
 11 ms 2608 KB 
#include "Joi.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 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]]); 
    }
}
#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

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: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1136 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 4 ms 1264 KB Output is correct
3 Incorrect 4 ms 1264 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -