oj.uz

Submission #59224

# Submission time Handle Problem Language Result Execution time Memory
59224 2018-07-21T08:54:27 Z alenam0161 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 47 ms 4200 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];
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);
        }
      }
}

#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;
    int lst=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;
            lst=to;
            if(is_good[to])return to;
            q.push({to,step+1});
        }
    }
    return lst;
}
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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1264 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3888 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4024 KB Output is correct
2 Correct 5 ms 4024 KB Output is correct
3 Correct 5 ms 4024 KB Output is correct
4 Correct 10 ms 4024 KB Output is correct
5 Correct 6 ms 4024 KB Output is correct
6 Correct 9 ms 4024 KB Output is correct
7 Correct 9 ms 4024 KB Output is correct
8 Correct 11 ms 4024 KB Output is correct
9 Correct 18 ms 4024 KB Output is correct
10 Correct 23 ms 4024 KB Output is correct
11 Correct 19 ms 4024 KB Output is correct
12 Correct 5 ms 4024 KB Output is correct
13 Correct 6 ms 4024 KB Output is correct
14 Correct 6 ms 4024 KB Output is correct
15 Correct 5 ms 4024 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4132 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 4200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -