oj.uz

Submission #1077597

# Submission time Handle Problem Language Result Execution time Memory
1077597 2024-08-27T08:12:54 Z danikoynov Amusement Park (JOI17_amusement_park) C++14
18 / 100
 17 ms 5172 KB 
#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 = 0; i < M; i ++)
  {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }

  dfs(0, 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);
}

#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(0);

  path.pop_back();
}

int bit_val[MAXBIT], ch[MAXBIT];

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 ++;

  /**for (int cur : path)
    cout << cur << " ";
  cout << endl;*/
  bit_val[linked[P]] = V;
  int ver = P;
  for (int step = 0; step < 240; step ++)
  {
    
    int nxt = (pos + 1) % (int)(path.size());
    //cout << "move from " << ver  << " " << path[nxt] << endl;
    bool fine = false;
    for (int j = 0; j < M; j ++)
    {
      if (A[j] == ver && B[j] == path[nxt])
        fine = true;
      if (A[j] == path[nxt] && B[j] == ver)
        fine = true;
    }
 
    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;
    pos = nxt;
  }


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

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

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:65:10: warning: variable 'fine' set but not used [-Wunused-but-set-variable]
   65 |     bool fine = false;
      |          ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1296 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 1 ms 1296 KB Output is correct
4 Correct 0 ms 1296 KB Output is correct
5 Correct 1 ms 1296 KB Output is correct
6 Correct 0 ms 1296 KB Output is correct
7 Correct 1 ms 1312 KB Output is correct
8 Correct 1 ms 1304 KB Output is correct
9 Correct 1 ms 1308 KB Output is correct
10 Correct 0 ms 1304 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 2 ms 1308 KB Output is correct
13 Correct 1 ms 1312 KB Output is correct
14 Correct 1 ms 1388 KB Output is correct
15 Correct 2 ms 1304 KB Output is correct
16 Correct 0 ms 1304 KB Output is correct
17 Correct 1 ms 1312 KB Output is correct
18 Correct 2 ms 1304 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4708 KB Output is correct
2 Correct 16 ms 4880 KB Output is correct
3 Correct 16 ms 4716 KB Output is correct
4 Correct 10 ms 3300 KB Output is correct
5 Correct 9 ms 3816 KB Output is correct
6 Correct 9 ms 3556 KB Output is correct
7 Correct 14 ms 3816 KB Output is correct
8 Correct 9 ms 3812 KB Output is correct
9 Correct 9 ms 3660 KB Output is correct
10 Correct 7 ms 3300 KB Output is correct
11 Correct 8 ms 3300 KB Output is correct
12 Correct 8 ms 3208 KB Output is correct
13 Correct 9 ms 3036 KB Output is correct
14 Correct 9 ms 3300 KB Output is correct
15 Correct 12 ms 3300 KB Output is correct
16 Correct 10 ms 3312 KB Output is correct
17 Correct 10 ms 3300 KB Output is correct
18 Correct 9 ms 3312 KB Output is correct
19 Correct 9 ms 3308 KB Output is correct
20 Incorrect 7 ms 3920 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1548 KB Output is correct
2 Correct 0 ms 1296 KB Output is correct
3 Correct 1 ms 1296 KB Output is correct
4 Correct 2 ms 1844 KB Output is correct
5 Correct 2 ms 1848 KB Output is correct
6 Correct 2 ms 2100 KB Output is correct
7 Correct 2 ms 1840 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 8 ms 4320 KB Output is correct
10 Correct 7 ms 4328 KB Output is correct
11 Correct 7 ms 4336 KB Output is correct
12 Correct 1 ms 1308 KB Output is correct
13 Correct 1 ms 1308 KB Output is correct
14 Correct 1 ms 1308 KB Output is correct
15 Correct 1 ms 1296 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 4720 KB Partially correct
2 Partially correct 17 ms 4932 KB Partially correct
3 Partially correct 17 ms 5172 KB Partially correct
4 Partially correct 10 ms 3400 KB Partially correct
5 Partially correct 10 ms 4420 KB Partially correct
6 Partially correct 9 ms 3916 KB Partially correct
7 Partially correct 10 ms 3920 KB Partially correct
8 Partially correct 10 ms 3664 KB Partially correct
9 Partially correct 9 ms 3912 KB Partially correct
10 Partially correct 9 ms 3560 KB Partially correct
11 Partially correct 9 ms 3400 KB Partially correct
12 Partially correct 10 ms 3372 KB Partially correct
13 Partially correct 7 ms 3380 KB Partially correct
14 Partially correct 10 ms 3336 KB Partially correct
15 Partially correct 9 ms 3360 KB Partially correct
16 Partially correct 11 ms 3352 KB Partially correct
17 Partially correct 13 ms 3396 KB Partially correct
18 Partially correct 9 ms 3396 KB Partially correct
19 Partially correct 9 ms 3480 KB Partially correct
20 Incorrect 7 ms 3908 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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