oj.uz

Submission #59218

# Submission time Handle Problem Language Result Execution time Memory
59218 2018-07-21T07:58:46 Z alenam0161 Amusement Park (JOI17_amusement_park) C++17
0 / 100
 20 ms 4568 KB 
#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];
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,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);
        }
      }
}

#include "Ioi.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 is_good[Mxn];
int par[Mxn];
void bfs(int x){
    memset(f,0,sizeof(f));
    queue<pair<int,int> >  q;
    q.push({x,1});
    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){
                og[to]=true;
            }
            if(step<120){
                q.push({to,step+1});
            }
            used[to]=f[to]=true;
        }
    }
}
int bfs_else(int x){
    memset(f,0,sizeof(f));
    queue<pair<int,int> >  q;
    q.push({x,1});
    f[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:g[v]){
            if(f[to])continue;
            par[to]=v;
            if(is_good[to])return to;
            q.push({to,step+1});
        }
    }
}
int bfs_fnd(int x){
    memset(f,0,sizeof(f));
    queue<pair<int,int> >  q;
    q.push({x,1});
    f[x]=true;
    par[x]=x;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        for(int to:g[v]){
            if(f[to])continue;
            par[to]=v;
            if(step==60)return to;
            q.push({to,step+1});
        }
    }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i=0;i<M;++i){
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    vector<int> v;
      for(int i = 0; i < N; i++){
        if(used[i]==false){
            bfs(i);
            v.push_back(i);
            is_good[i]=true;
        }
      }
   int x=bfs_else(P);
   vector<int> all;
   int lst=V;
   all.push_back(V);
   while(x!=par[x]){
        x=par[x];
        lst=Move(x);
        all.push_back(lst);
   }
   if(all.size()>=60){
    long long ans=0;
    for(int ast=0;ast<60;++ast){
        ans+=(1ll<<ast)&all[all.size()-1-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++;
        ans+=(1ll<<ast)&(lst);
    }

  return ans;
}

Compilation message

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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