제출 #1077689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077689		danikoynov	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	4 ms	1564 KiB

Joi

#include "Joi.h"


#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 10010, MAXBIT = 60;
vector < int > adj[MAXN];
int used[MAXN], acord[MAXN];
vector < int > ord;

int last_bit;
void dfs(int v, ll X)
{
  used[v] = 1;
  acord[v] = last_bit;

  /**if (last_bit == 59)
  {
    cout << "info " << (X & ((ll)(1) << last_bit)) << " " << ((X & ((ll)(1) << last_bit)) > 0) << endl;
  }*/
  ///cout << "Vertex " << v << " " << last_bit << endl;
  MessageBoard(v, ((X & ((ll)(1) << last_bit)) > 0));  
  last_bit ++;
  if (last_bit == MAXBIT)
    last_bit = 0;
  ord.push_back(v);
  for (int u : adj[v])
  { 

    if (used[u])
      continue;
    dfs(u, X);
    ord.push_back(v);
  }
}

void build_tree(int N, int M, int A[], int B[], ll X)
{
  for (int i = M - 1; i < M; i ++)
  {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }

  dfs(32, X);

  ord.pop_back();
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  build_tree(N, M, A, B, X);
}

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 10010, MAXBIT = 60;
vector < int > graph[MAXN];
int marked[MAXN], linked[MAXN];
vector < int > path;

int next_bit;
void dfs(int v)
{
  marked[v] = 1;
  linked[v] = next_bit ++;
  if (next_bit == MAXBIT)
    next_bit = 0;
  //MessageBoard(v, ((X & ((ll)(1) << bit)) > 0));
  path.push_back(v);
  for (int u : graph[v])
  { 
    if (marked[u])
      continue;
    dfs(u);
    path.push_back(v);
  }
}

void build_tree(int N, int M, int A[], int B[])
{
  for (int i = 0; i < M; i ++)
  {
    graph[A[i]].push_back(B[i]);
    graph[B[i]].push_back(A[i]);
  }

  dfs(32);

  path.pop_back();
}

int bit_val[MAXBIT], ch[MAXBIT];

int min_step[MAXN], from[MAXN];
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) 
{
  build_tree(N, M, A, B);

  
  int pos = 0;
  while(path[pos] != P)
    pos ++;

  vector < int > tk = path;
  for (int cur : tk)
    path.push_back(cur);

  /**for (int cur : path)
    cout << cur << " ";
  cout << endl;*/
  bit_val[linked[P]] = V;
  ch[linked[P]] = 1;
  int ver = P;
  for (int i = 0; i < N; i ++)
  {
    min_step[i] = 4 * N;
    from[i] = -1;
  }

  
  for (int s = 0; s < tk.size(); s ++)
  {
    ll ds = 0;
    int pivot = s;
    while(pivot < path.size())
    {
      //cout << s << " : " << pivot << " " << ds << " " << endl;
      ds |= ((ll)(1) << linked[path[pivot]]);
      if (ds == ((ll)(1) << MAXBIT) - 1)
        break;
      pivot ++;
    }

    assert(pivot < path.size());
    if (pivot - s < min_step[path[s]])
    {
      from[path[s]] = s;
      min_step[path[s]] = pivot - s;
    }

  }
  ll ds = 0;
  bool done = false;
  int best_to = -1, best_val = 300;
  for (int to = 0; to < 120; to ++)
  {
    if (to + min_step[path[pos + to]] <= best_val)
    {
      best_val = to + min_step[path[pos + to]];
      best_to = to;
    }
  }

  
  assert(best_to != - 1);
  int to = best_to;

  for (int d = 1; d <= to; d ++)
  {
    bit_val[linked[path[pos + d]]] = Move(path[pos + d]);
    ch[linked[path[pos + d]]] = 1;
    ///cout << "add " << linked[path[pos + d]];
  }
  ver = path[pos + to];
  for (int d = 1; d <= min_step[ver]; d ++)
  {
    bit_val[linked[path[from[ver] + d]]] = Move(path[from[ver] + d]);
    ch[linked[path[from[ver] + d]]] = 1;
    ///cout << "add " << linked[path[from[ver] + d]] << endl;
  }
  done = true;
  /*
  for (int step = 0; ds != ((ll)(1) << MAXBIT) - 1; step ++)
  {
    
    int nxt = (pos + 1) % (int)(path.size());
    //cout << "move from " << ver  << " " << path[nxt] << endl;
 
    ver = path[nxt];  
    int res = Move(ver);   
    ///assert(step != 119);
    //cout << "linked " << linked[ver] << " " << res << endl;
    bit_val[linked[ver]] = res;
    ch[linked[ver]] = 1;
    ds |= ((ll)(1) << linked[ver]);
    pos = nxt;
  }*/


  ll X = 0;
  for (int bit = 0; bit < MAXBIT; bit ++)
  {
    //if (ch[bit] == 0)
      //cout << "FUCK " << bit << endl;
    assert(ch[bit]);
    if (bit_val[bit] > 0)
      X |= ((ll)(1) << bit);
  }

  //cout << "X " << X << endl;
  return X;
}

컴파일 시 표준 에러 (stderr) 메시지

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int s = 0; s < tk.size(); s ++)
      |                   ~~^~~~~~~~~~~
Ioi.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(pivot < path.size())
      |           ~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Ioi.cpp:3:
Ioi.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     assert(pivot < path.size());
      |            ~~~~~~^~~~~~~~~~~~~
Ioi.cpp:94:6: warning: unused variable 'ds' [-Wunused-variable]
   94 |   ll ds = 0;
      |      ^~
Ioi.cpp:95:8: warning: variable 'done' set but not used [-Wunused-but-set-variable]
   95 |   bool done = false;
      |        ^~~~

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