Submission #236755

# Submission time Handle Problem Language Result Execution time Memory
236755 2020-06-03T08:31:06 Z AlexLuchianov Amusement Park (JOI17_amusement_park) C++14
0 / 100
46 ms 5096 KB
#include "Joi.h"
#include <vector>
#include <cassert>
#include <iostream>

using ll = long long;

namespace {
  int const nmax = 10000;
  int const sigma = 60;

  std::vector<int> g[1 + nmax];
  std::vector<int> ord, id, pos;

  void initialize(int n){
    id.resize(1 + n);
    pos.resize(1 + n);
    for(int i = 0;i < n; i++)
      id[i] = -1;  
  }

  void dfs(int node, int &ptr){
    ord.push_back(node);  
    pos[node] = ord.size() - 1;
    id[node] = (ptr++) % sigma;
    
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(id[to] == -1){
	dfs(to, ptr);
	ord.push_back(node);
      }
    }
  }
};

void Joi(int n, int m, int A[], int B[], long long X, int T) {
  for(int i = 0; i < m; i++){
    int x = A[i], y = B[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  initialize(n);
  int ptr = 0;
  dfs(0, ptr);
  for(int i = 0; i < n; i++) {
    assert(0 <= id[i]);
    MessageBoard(i, 0 < (X & (1LL << id[i])));
  }
}
#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <cassert>

namespace {
  int const nmax = 10000;
  int const sigma = 60;

  std::vector<int> g[1 + nmax];
  std::vector<int> ord, id, pos;

  void initialize(int n){
    id.resize(1 + n);
    pos.resize(1 + n);
    for(int i = 0;i < n; i++)
      id[i] = -1;  
  }

  void dfs(int node, int &ptr){
    ord.push_back(node);  
    pos[node] = ord.size() - 1;
    id[node] = (ptr++) % sigma;
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(id[to] == -1){
	dfs(to, ptr);
	ord.push_back(node);
      }
    }
  }
};

long long Ioi(int n, int m, int A[], int B[], int P, int value, int T) {
  for(int i = 0; i < m; i++){
    int x = A[i], y = B[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int ptr = 0;
  initialize(n);
  dfs(1, ptr);
  long long val = value;
  long long solution = (val<<id[P]);
  int curr = pos[P];

  for(int i = 0; i < sigma * 2; i++){
    curr++;
    if(curr == ord.size())
      curr = 1;
    val = Move(ord[curr]);
    solution |= (val<<id[ord[curr]]);
  }
  return solution;
}

Compilation message

Joi.cpp: In function 'void {anonymous}::dfs(int, int&)':
Joi.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~

Ioi.cpp: In function 'void {anonymous}::dfs(int, int&)':
Ioi.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(curr == ord.size())
        ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1420 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 5096 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 1172 KB Output is correct
2 Correct 10 ms 1152 KB Output is correct
3 Correct 10 ms 1160 KB Output is correct
4 Correct 11 ms 1744 KB Output is correct
5 Correct 13 ms 1752 KB Output is correct
6 Correct 11 ms 1980 KB Output is correct
7 Correct 11 ms 1744 KB Output is correct
8 Correct 12 ms 1868 KB Output is correct
9 Correct 23 ms 4420 KB Output is correct
10 Correct 27 ms 4512 KB Output is correct
11 Correct 22 ms 4432 KB Output is correct
12 Correct 11 ms 1288 KB Output is correct
13 Incorrect 10 ms 1304 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4812 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 5064 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -