Submission #796770

#	Time	Username	Problem	Language	Result	Execution time	Memory
796770		anton	Amusement Park (JOI17_amusement_park)	C++17	0 / 100	18 ms	4876 KiB

Joi

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

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

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

  for(auto v: adj[u]){
    if(!vis[v]){
      dfs(v, u);
    }
  }
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(int i = 0; i<K; i++){
    if((X&(1LL<<i))>0){
      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;
int x2[K], mod[MAX_N], anc[MAX_N], sz[MAX_N];
bool vis2[MAX_N], found[K];
int nb_vis =0;
vector<int> order2;
vector<int> adj2[MAX_N];

void dfs2(int u, int a){
  vis2[u] = true;
  anc[u] =a;
  mod[u] = nb_vis;
  nb_vis++;
  order2.push_back(u);
  sz[u] =1;

  for(auto v: adj2[u]){
    if(!vis2[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;
  }
}
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);

  while(sz[cur]<K){
    //cout<<anc[cur]<<endl;
    int val =Move(anc[cur]);
    cur = anc[cur];
    find(mod[cur]%K, val);
  }

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

  int res= 0;
  for(int i = 0; i<K; i++){
    if(x2[i]){
      res+=(1LL<<i);
    }
  }
  //cout<<res<<endl;
  return res;
}

Compilation message (stderr)

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:62:12: warning: unused variable 'e' [-Wunused-variable]
   62 |   for(auto e: order2){
      |            ^

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