Submission #796830

#	Time	Username	Problem	Language	Result	Execution time	Memory
796830		anton	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	19 ms	5484 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;

static const int MAX_N = 1e4;
static const int K = 60;
static int x[K];
static bool vis[MAX_N];
static vector<int> order;
static vector<int> adj[MAX_N];

void dfs(int u, int a){
  MessageBoard(u, x[order.size()%K]);
  //cout<<u<<endl;
  order.push_back(u);
  vis[u] = true;

  for(auto v: adj[u]){
    if(!vis[v]){
      dfs(v, u);
    }
  }
  //cout<<u<<endl;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(long long i = 0; i<K; i++){
    if((X&(1LL<<i))>0LL){
      x[i] = 1;
    }
    else{
      x[i] = 0;
    }
    //cout<<x[i]<<" ";
  }

  for(int i = 0; i<M; i++){
    int a, b;
    a = A[i];
    b =B[i];
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, -1);
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4;
const int K = 60;
static int x2[K], mod[MAX_N], anc[MAX_N], sz[MAX_N], place[MAX_N], among_peers[MAX_N];
static bool vis2[MAX_N], found[K];
static int nb_vis =0;
static vector<int> order2;
static vector<int> adj2[MAX_N];
static vector<int> ch[MAX_N];

void dfs2(int u, int a){
  vis2[u] = true;
  anc[u] =a;
  mod[u] = nb_vis;
  place[u] = order2.size();
  nb_vis++;
  ////cout<<u<<" "<<mod[u]<<endl;
  order2.push_back(u);
  sz[u] =1;

  for(auto v: adj2[u]){
    if(!vis2[v]){
      among_peers[v] = ch[u].size();
      ch[u].push_back(v);
      dfs2(v, u);
      sz[u] += sz[v];
      order2.push_back(u);
    }
  }

}
int nb_found = 0;

void find(int id, int v){
  if(!found[id]){
    found[id] = true;
    nb_found++;
    x2[id] = v;
  }
}

void explore_after(int u, int order){
  //cout<<"exploring "<<u<<" after "<<order<<endl;
  //cout<<mod[u]<<endl;
  for(int i = order; i<ch[u].size() && nb_found<K; i++){
    int next = ch[u][i];
    int val = Move(next);
    find(mod[next]%K, val);
    explore_after(next, 0);
    if(nb_found<K){
      Move(u);
    }
  }
  //cout<<"done "<<u<<endl;
}

void explore_before(int u, int order){
  //cout<<"exploring "<<u<<" before "<<order<<endl;
  //cout<<mod[u]<<endl;
  for(int i = order; i>=0 && nb_found<K; i--){
    int next = ch[u][i];
    int val = Move(next);
    find(mod[next]%K, val);
    explore_before(next, ch[next].size()-1);
    if(nb_found<K){
      Move(u);
    }
  }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {

  for(int i = 0; i<M; i++){
    int a, b;
    a = A[i];
    b =B[i];
    adj2[a].push_back(b);
    adj2[b].push_back(a);
  }

  dfs2(0, -1);

  int cur = P;
  find(mod[cur]%K, V);
  for(int i= 0; i< order2.size(); i++){
    ////cout<<i<<" "<<order2[i]<<" | ";
  }
  ////cout<<endl;

  explore_after(cur, 0);
  //explore_before(cur, ch[cur].size()-1);
  while(nb_found<K){
    ////cout<<anc[cur]<<endl;
    int val =Move(anc[cur]);
    
    find(mod[anc[cur]]%K, val);
    explore_after(anc[cur], among_peers[cur]+1);
    if(sz[anc[cur]]<K){
      explore_before(anc[cur], among_peers[cur]-1);
    }
    //explore_before(anc[cur], among_peers[cur]-1);
    cur = anc[cur];
  }

  /*////cout<<"done going up "<<cur<<" "<<endl;
  int pos = place[cur]+1;
  ////cout<<"first at "<<pos<<endl;
  for(int i = pos; nb_found<K; i++){
    ////cout<<"going to "<<order2[i]<<endl;
    int val =Move(order2[i]);
    cur= order2[i];
    find(mod[cur]%K, val); 
  }*/

  long long res= 0;
  for(long long i = 0; i<K; i++){
    if(x2[i]){
      res+=(1LL<<i);
    }
  }

  ////cout<<res<<endl;
  return res;
}

Compilation message (stderr)

Ioi.cpp: In function 'void explore_after(int, int)':
Ioi.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = order; i<ch[u].size() && nb_found<K; i++){
      |                      ~^~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i= 0; i< order2.size(); i++){
      |                 ~^~~~~~~~~~~~~~~

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