oj.uz

Submission #699884

# Submission time Handle Problem Language Result Execution time Memory
699884 2023-02-18T07:55:26 Z cig32 Amusement Park (JOI17_amusement_park) C++17
0 / 100
 25 ms 4276 KB 
#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;

static vector<int> adj2[12269];
static bool vis2[12269];
static int val2[12269];
static int nxt2;
static void dfs2(int node, long long X, int par) {
  val2[node] = nxt2;
  nxt2 = (nxt2 + 1) % 60;
  long long res = (X & (1ll << val2[node]));
  if(res > 0) res = 1;
  MessageBoard(node, (int) res);
  vis2[node] = 1;
  for(int x: adj2[node]) {
    if(!vis2[x]) {
      dfs2(x, X, node);
    }
  }
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(int i=0; i<M; i++) {
    adj2[A[i]].push_back(B[i]);
    adj2[B[i]].push_back(A[i]);
  }
  for(int i=0; i<N; i++) {
    sort(adj2[i].begin(), adj2[i].end());
  }
  for(int i=0; i<N; i++) {
    vis2[i] = 0;
  }
  dfs2(0, X, -1);
}

#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e4 + 10;
static vector<int> adj[MAXN];
static bool vis[MAXN];
static int val[MAXN];
static int nxt;
static vector<int> et;
static void dfs(int node, int par) {
  val[node] = nxt;
  nxt = (nxt+1) % 60;
  vis[node] = 1;
  et.push_back(node);
  for(int x: adj[node]) {
    if(!vis[x]) {
      dfs(x, node);
      et.push_back(node);
    }
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  nxt = 0;
  et.clear();
  for(int i=0; i<N; i++) {
    adj[i].clear();
  }
  for(int i=0; i<M; i++) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  for(int i=0; i<N; i++) {
    sort(adj[i].begin(), adj[i].end());
  }
  for(int i=0; i<N; i++) {
    vis[i] = 0;
  }
  dfs(0, -1);
  long long ans = 0;
  int res[60];
  for(int i=0; i<60; i++) res[i] = 0;
  res[val[P]] = V;
  int l[N];
  for(int i=0; i<N; i++) l[i] = -1;
  for(int i=0; i<et.size(); i++) {
    if(l[et[i]] == -1) l[et[i]] = i;
  }
  int node = P, idx = l[P];
  
  int c=240;

  for(int i=max(0, idx-c); i<=idx; i++) {
    // [i, i+c]
    set<int> st;
    for(int j=i; j<=min(i+c, (int) et.size() - 1); j++) st.insert(val[et[j]]);
    if(st.size() == 60) {
      cout << "YES!\n";
      if(idx-i <= min(i+c-idx, (int)et.size()-1-idx)) {
        while(idx-1 >= i) {
          idx--;
          int rm = Move(et[idx]);
          node = et[idx];
          res[val[node]] = rm;
        }
        while(idx+1 <= i+c && idx+1 < et.size()) {
          idx++;
          int rm = Move(et[idx]);
          node = et[idx];
          res[val[node]] = rm;
        }
      }
      else {
        while(idx+1 <= i+c && idx+1 < et.size()) {
          idx++;
          int rm = Move(et[idx]);
          node = et[idx];
          res[val[node]] = rm;
        }
        while(idx-1 >= i) {
          idx--;
          int rm = Move(et[idx]);
          node = et[idx];
          res[val[node]] = rm;
        }
      }
    }
  }
  for(int i=0; i<60; i++) {
    if(res[i]) ans += (1ll << i);
  }
  return ans;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i=0; i<et.size(); i++) {
      |                ~^~~~~~~~~~
Ioi.cpp:66:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         while(idx+1 <= i+c && idx+1 < et.size()) {
      |                               ~~~~~~^~~~~~~~~~~
Ioi.cpp:74:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(idx+1 <= i+c && idx+1 < et.size()) {
      |                               ~~~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1152 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4204 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1160 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4184 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 4276 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -