oj.uz

Submission #699885

# Submission time Handle Problem Language Result Execution time Memory
699885 2023-02-18T07:56:04 Z cig32 Amusement Park (JOI17_amusement_park) C++17
8 / 100
 23 ms 4244 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) {
      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:65:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while(idx+1 <= i+c && idx+1 < et.size()) {
      |                               ~~~~~~^~~~~~~~~~~
Ioi.cpp:73:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while(idx+1 <= i+c && idx+1 < et.size()) {
      |                               ~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1160 KB Output is correct
2 Correct 1 ms 1164 KB Output is correct
3 Correct 2 ms 1164 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 0 ms 1152 KB Output is correct
6 Correct 1 ms 1160 KB Output is correct
7 Correct 2 ms 1156 KB Output is correct
8 Correct 2 ms 1176 KB Output is correct
9 Correct 1 ms 1156 KB Output is correct
10 Correct 1 ms 1176 KB Output is correct
11 Correct 5 ms 1488 KB Output is correct
12 Correct 0 ms 1160 KB Output is correct
13 Correct 2 ms 1160 KB Output is correct
14 Correct 2 ms 1164 KB Output is correct
15 Correct 2 ms 1164 KB Output is correct
16 Correct 2 ms 1156 KB Output is correct
17 Correct 2 ms 1156 KB Output is correct
18 Correct 2 ms 1164 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4172 KB Output is correct
2 Correct 23 ms 4168 KB Output is correct
3 Correct 20 ms 4220 KB Output is correct
4 Correct 14 ms 2888 KB Output is correct
5 Correct 12 ms 3276 KB Output is correct
6 Correct 13 ms 3140 KB Output is correct
7 Correct 12 ms 3140 KB Output is correct
8 Correct 12 ms 3248 KB Output is correct
9 Correct 12 ms 3268 KB Output is correct
10 Correct 11 ms 2884 KB Output is correct
11 Correct 12 ms 2880 KB Output is correct
12 Correct 11 ms 2728 KB Output is correct
13 Correct 11 ms 2748 KB Output is correct
14 Correct 12 ms 2728 KB Output is correct
15 Correct 14 ms 2768 KB Output is correct
16 Correct 12 ms 2756 KB Output is correct
17 Correct 12 ms 2892 KB Output is correct
18 Correct 12 ms 2912 KB Output is correct
19 Correct 12 ms 2876 KB Output is correct
20 Incorrect 12 ms 3396 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Partially correct 23 ms 4164 KB Partially correct
2 Partially correct 20 ms 4176 KB Partially correct
3 Partially correct 23 ms 4244 KB Partially correct
4 Partially correct 14 ms 2872 KB Partially correct
5 Partially correct 12 ms 3648 KB Partially correct
6 Partially correct 12 ms 3212 KB Partially correct
7 Partially correct 14 ms 3180 KB Partially correct
8 Partially correct 14 ms 2992 KB Partially correct
9 Partially correct 13 ms 3120 KB Partially correct
10 Partially correct 12 ms 2996 KB Partially correct
11 Partially correct 12 ms 3012 KB Partially correct
12 Partially correct 11 ms 2744 KB Partially correct
13 Partially correct 11 ms 2748 KB Partially correct
14 Partially correct 11 ms 2748 KB Partially correct
15 Partially correct 12 ms 2876 KB Partially correct
16 Partially correct 12 ms 2764 KB Partially correct
17 Partially correct 12 ms 2792 KB Partially correct
18 Partially correct 13 ms 2980 KB Partially correct
19 Partially correct 13 ms 2840 KB Partially correct
20 Incorrect 12 ms 3396 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4168 KB Output isn't correct
2 Halted 0 ms 0 KB -