Submission #59223

#	Time	Username	Problem	Language	Result	Execution time	Memory
59223		alenam0161	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	45 ms	6128 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
const int Mxn = 10007;
bool used[Mxn];
bool f[Mxn];
vector<int> g[Mxn];
bool og[Mxn];
bool gt(long long x){
    return x==0ll ? 0:1;
}
void bfs(int x,long long Val){
    memset(f,0,sizeof(f));
    queue<pair<int,int> >  q;
    q.push({x,1});
    MessageBoard(x,Val&(1ll));
    f[x]=true;
    used[x]=true;
    og[x]=true;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        if(step==120)break;
        for(int to:g[v]){
            if(f[to])continue;
            if(step>59&&used[to])continue;
            if(step<=59){
                MessageBoard(to,gt(Val&(1ll<<step)));
                og[to]=true;
            }
            if(step<120){
                q.push({to,step+1});
            }
            used[to]=f[to]=true;
        }
    }
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
    for(int i=0;i<M;++i){
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
      for(int i = 0; i < N; i++){
        if(used[i]==false)bfs(i,X);
      }
      for(int i=0;i<N;++i){
        if(og[i]==false){
            MessageBoard(i,0);
        }
      }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
const int Mxn = 10007;
bool ussd[Mxn];
bool ff[Mxn];
vector<int> gg[Mxn];
bool is_good[Mxn];
int par[Mxn];
void bfs(int x){
    memset(ff,0,sizeof(ff));
    queue<pair<int,int> >  q;
    q.push({x,1});
    ff[x]=true;
    ussd[x]=true;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        if(step==120)break;
        for(int to:gg[v]){
            if(ff[to])continue;
            if(step>59&&ussd[to])continue;
            if(step<120){
                q.push({to,step+1});
            }
            ussd[to]=ff[to]=true;
        }
    }
}
int bfs_else(int x){
    memset(ff,0,sizeof(ff));
    queue<pair<int,int> >  q;
    q.push({x,1});
    ff[x]=true;
    par[x]=x;
    if(is_good[x])return x;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        if(step==120)break;
        for(int to:gg[v]){
            if(ff[to])continue;
            par[to]=v;
            ff[to]=true;
            if(is_good[to])return to;
            q.push({to,step+1});
        }
    }
}
int bfs_fnd(int x){
    memset(ff,0,sizeof(ff));
    queue<pair<int,int> >  q;
    q.push({x,1});
    ff[x]=true;
    par[x]=x;
    int ls=x;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        for(int to:gg[v]){
            if(ff[to])continue;
            par[to]=v;
            ls=to;
            ff[to]=true;
            if(step==60)return to;
            q.push({to,step+1});
        }
    }
    return ls;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i=0;i<M;++i){
        gg[A[i]].push_back(B[i]);
        gg[B[i]].push_back(A[i]);
    }
    vector<int> v;
      for(int i = 0; i < N; i++){
        if(ussd[i]==false){
            bfs(i);
            v.push_back(i);
            is_good[i]=true;
        }
      }
   int x=bfs_else(P);
   vector<int> all;
   int lst=V;
   vector<int> nf;
   vector<int> nf_ans;
    all.push_back(V);
    int o=x;
   while(o!=par[o]){
        nf.push_back(o);
        o=par[o];
   }
    for(int i=nf.size()-1;i>=0;i--){
        nf_ans.push_back(Move(nf[i]));
        lst=nf_ans.back();
        all.push_back(lst);
    }
   if(all.size()>=60){
    long long ans=0;
    for(int ast=0;ast<60;++ast){
        if(all[all.size()-1-ast])
        ans+=(1ll<<ast);
    }
    return ans;
   }
  int oth=bfs_fnd(x);
  vector<int> nw;
  nw.push_back(lst);
  long long ans=lst;
  int ast=0;
  vector<int> perm;
  while(x!=oth){
    perm.push_back(oth);
    oth=par[oth];
  }
    for(int i=perm.size()-1;i>=0;i--){
        lst=Move(perm[i]);
        ast++;
        if(lst)
        ans+=(1ll<<ast);
    }

  return ans;
}

Compilation message (stderr)

Ioi.cpp: In function 'int bfs_else(int)':
Ioi.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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