oj.uz

Submission #1039489

# Submission time Handle Problem Language Result Execution time Memory
1039489 2024-07-31T00:37:19 Z juicy Amusement Park (JOI17_amusement_park) C++17
100 / 100
 31 ms 35148 KB 
#include "Joi.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  bitset<10000> G[10000];
  vector<int> g[10000];
  bool vis[10000];  
  int pos[10000], pr[10000], c[10000];
  int timer = 0;

  void dfs(int u) {
    vis[u] = 1;
    pos[timer++] = u;
    for (int v : g[u]) {
      if (!vis[v]) {
        G[u][v] = G[v][u] = 1;
        pr[v] = u;
        dfs(v);
      }
    }
  }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  dfs(0);
  vector<int> tr;
  for (int i = 0; i < 60; ++i) {
    tr.push_back(pos[i]);
    c[pos[i]] = i;
  }
  vector<vector<int>> tree(N);
  for (int u : tr) {
    tree[u] = tr;
  }
  for (int i = 60; i < N; ++i) {
    int u = pos[i], p = pr[u];
    auto &tr = tree[u];
    tr = tree[p];
    int d = -1;
    for (int x : tr) {
      if (x != p) {
        int deg = 0;
        for (int y : tr) {
          if (G[x][y]) {
            ++deg;
          }
        }
        if (deg == 1) {
          d = x;
          break;
        }
      }
    }
    c[u] = c[d];
    tr.erase(find(tr.begin(), tr.end(), d));
    tr.push_back(u);
  }
  for (int i = 0; i < N; ++i) {
    MessageBoard(i, X >> c[i] & 1);
  }
}
#include "Ioi.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  void __print() {
    cerr << "]\n";
  }

  template<class T, class... V> 
  void __print(T t, V... v) {
    cerr << t;
    if (sizeof...(v)) {
      cerr << ", ";
    }
    __print(v...);
  }

  #define debug(x...) cerr << "[" << #x << "] = ["; __print(x); 

  bitset<10000> G[10000];
  vector<int> g[10000], gph[10000];
  bool vis[10000];  
  int pos[10000], pr[10000], c[10000], val[10000];
  int timer = 0;

  void dfs(int u) {
    vis[u] = 1;
    pos[timer++] = u;
    for (int v : g[u]) {
      if (!vis[v]) {
        G[u][v] = G[v][u] = 1;
        pr[v] = u;
        dfs(v);
      }
    }
  }

  void DFS(int u) {
    vis[u] = 1;
    for (int v : gph[u]) {
      if (!vis[v]) {
        val[v] = Move(v);
        DFS(v);
        Move(u);
      }
    }
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  dfs(0);
  vector<int> tr;
  for (int i = 0; i < 60; ++i) {
    tr.push_back(pos[i]);
    c[pos[i]] = i;
  }
  vector<vector<int>> tree(N);
  for (int u : tr) {
    tree[u] = tr;
  }
  for (int i = 60; i < N; ++i) {
    int u = pos[i], p = pr[u];
    auto &tr = tree[u];
    tr = tree[p];
    int d = -1;
    for (int x : tr) {
      if (x != p) {
        int deg = 0;
        for (int y : tr) {
          if (G[x][y]) {
            ++deg;
          }
        }
        if (deg == 1) {
          d = x;
          break;
        }
      }
    }
    c[u] = c[d];
    tr.erase(find(tr.begin(), tr.end(), d));
    tr.push_back(u);
  }
  val[P] = V;
  for (int x : tree[P]) {
    for (int y : tree[P]) {
      if (G[x][y]) {
        gph[x].push_back(y);
        gph[y].push_back(x);
      }
    }
  }
  fill(vis, vis + N, 0);
  DFS(P);
  long long res = 0;
  for (int x : tree[P]) {
    if (val[x]) {
      res += 1LL << c[x];
    }
  }
  return res;
}

Compilation message

Ioi.cpp:8:8: warning: 'void {anonymous}::__print()' defined but not used [-Wunused-function]
    8 |   void __print() {
      |        ^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4876 KB Output is correct
2 Correct 1 ms 4892 KB Output is correct
3 Correct 2 ms 5148 KB Output is correct
4 Correct 0 ms 4892 KB Output is correct
5 Correct 1 ms 4892 KB Output is correct
6 Correct 1 ms 4892 KB Output is correct
7 Correct 2 ms 5144 KB Output is correct
8 Correct 2 ms 5152 KB Output is correct
9 Correct 2 ms 5144 KB Output is correct
10 Correct 2 ms 4892 KB Output is correct
11 Correct 3 ms 5444 KB Output is correct
12 Correct 1 ms 4884 KB Output is correct
13 Correct 1 ms 5156 KB Output is correct
14 Correct 2 ms 5156 KB Output is correct
15 Correct 2 ms 5156 KB Output is correct
16 Correct 2 ms 5156 KB Output is correct
17 Correct 2 ms 5148 KB Output is correct
18 Correct 2 ms 5148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 34672 KB Output is correct
2 Correct 22 ms 35120 KB Output is correct
3 Correct 22 ms 35116 KB Output is correct
4 Correct 16 ms 33092 KB Output is correct
5 Correct 16 ms 33880 KB Output is correct
6 Correct 16 ms 33604 KB Output is correct
7 Correct 16 ms 33764 KB Output is correct
8 Correct 17 ms 33868 KB Output is correct
9 Correct 16 ms 33868 KB Output is correct
10 Correct 13 ms 33356 KB Output is correct
11 Correct 15 ms 33360 KB Output is correct
12 Correct 17 ms 32056 KB Output is correct
13 Correct 17 ms 32044 KB Output is correct
14 Correct 17 ms 32380 KB Output is correct
15 Correct 19 ms 33132 KB Output is correct
16 Correct 19 ms 33180 KB Output is correct
17 Correct 17 ms 33112 KB Output is correct
18 Correct 19 ms 33104 KB Output is correct
19 Correct 15 ms 33096 KB Output is correct
20 Correct 13 ms 33864 KB Output is correct
21 Correct 12 ms 33608 KB Output is correct
22 Correct 15 ms 33504 KB Output is correct
23 Correct 15 ms 33856 KB Output is correct
24 Correct 17 ms 33632 KB Output is correct
25 Correct 16 ms 33632 KB Output is correct
26 Correct 16 ms 33872 KB Output is correct
27 Correct 17 ms 33928 KB Output is correct
28 Correct 17 ms 33860 KB Output is correct
29 Correct 19 ms 32560 KB Output is correct
30 Correct 16 ms 32832 KB Output is correct
31 Correct 2 ms 4896 KB Output is correct
32 Correct 2 ms 4884 KB Output is correct
33 Correct 2 ms 5156 KB Output is correct
34 Correct 2 ms 4900 KB Output is correct
35 Correct 2 ms 4896 KB Output is correct
36 Correct 1 ms 4896 KB Output is correct
37 Correct 1 ms 4884 KB Output is correct
38 Correct 1 ms 4880 KB Output is correct
39 Correct 1 ms 4896 KB Output is correct
40 Correct 1 ms 4896 KB Output is correct
41 Correct 1 ms 4880 KB Output is correct
42 Correct 1 ms 4896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4892 KB Output is correct
2 Correct 1 ms 4892 KB Output is correct
3 Correct 1 ms 4880 KB Output is correct
4 Correct 2 ms 10552 KB Output is correct
5 Correct 3 ms 10552 KB Output is correct
6 Correct 3 ms 10548 KB Output is correct
7 Correct 2 ms 10556 KB Output is correct
8 Correct 3 ms 10552 KB Output is correct
9 Correct 13 ms 34228 KB Output is correct
10 Correct 13 ms 34028 KB Output is correct
11 Correct 14 ms 33956 KB Output is correct
12 Correct 1 ms 4888 KB Output is correct
13 Correct 1 ms 4892 KB Output is correct
14 Correct 1 ms 4892 KB Output is correct
15 Correct 0 ms 4892 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 34612 KB Output is correct
2 Correct 23 ms 35124 KB Output is correct
3 Correct 26 ms 35104 KB Output is correct
4 Correct 17 ms 33096 KB Output is correct
5 Correct 19 ms 34420 KB Output is correct
6 Correct 15 ms 33868 KB Output is correct
7 Correct 17 ms 33872 KB Output is correct
8 Correct 15 ms 33636 KB Output is correct
9 Correct 15 ms 33608 KB Output is correct
10 Correct 14 ms 33360 KB Output is correct
11 Correct 15 ms 33364 KB Output is correct
12 Correct 17 ms 31956 KB Output is correct
13 Correct 15 ms 32044 KB Output is correct
14 Correct 17 ms 32316 KB Output is correct
15 Correct 15 ms 33128 KB Output is correct
16 Correct 17 ms 33116 KB Output is correct
17 Correct 17 ms 33096 KB Output is correct
18 Correct 16 ms 33144 KB Output is correct
19 Correct 19 ms 33056 KB Output is correct
20 Correct 13 ms 33888 KB Output is correct
21 Correct 12 ms 33620 KB Output is correct
22 Correct 20 ms 34280 KB Output is correct
23 Correct 16 ms 33608 KB Output is correct
24 Correct 17 ms 33604 KB Output is correct
25 Correct 17 ms 33868 KB Output is correct
26 Correct 16 ms 33868 KB Output is correct
27 Correct 19 ms 33980 KB Output is correct
28 Correct 16 ms 33608 KB Output is correct
29 Correct 15 ms 32560 KB Output is correct
30 Correct 16 ms 32860 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 34712 KB Output is correct
2 Correct 22 ms 35148 KB Output is correct
3 Correct 22 ms 35020 KB Output is correct
4 Correct 18 ms 33100 KB Output is correct
5 Correct 18 ms 34720 KB Output is correct
6 Correct 19 ms 33580 KB Output is correct
7 Correct 19 ms 33608 KB Output is correct
8 Correct 16 ms 33860 KB Output is correct
9 Correct 15 ms 33620 KB Output is correct
10 Correct 19 ms 33352 KB Output is correct
11 Correct 15 ms 33356 KB Output is correct
12 Correct 17 ms 32060 KB Output is correct
13 Correct 16 ms 31860 KB Output is correct
14 Correct 17 ms 32316 KB Output is correct
15 Correct 17 ms 33096 KB Output is correct
16 Correct 16 ms 33088 KB Output is correct
17 Correct 19 ms 33092 KB Output is correct
18 Correct 17 ms 33160 KB Output is correct
19 Correct 20 ms 33092 KB Output is correct
20 Correct 13 ms 33884 KB Output is correct
21 Correct 13 ms 33612 KB Output is correct
22 Correct 17 ms 33604 KB Output is correct
23 Correct 16 ms 33820 KB Output is correct
24 Correct 16 ms 33608 KB Output is correct
25 Correct 15 ms 33608 KB Output is correct
26 Correct 17 ms 33616 KB Output is correct
27 Correct 16 ms 34120 KB Output is correct
28 Correct 16 ms 34120 KB Output is correct
29 Correct 15 ms 32868 KB Output is correct
30 Correct 15 ms 32832 KB Output is correct
31 Correct 2 ms 4896 KB Output is correct
32 Correct 1 ms 4876 KB Output is correct
33 Correct 1 ms 5156 KB Output is correct
34 Correct 1 ms 4896 KB Output is correct
35 Correct 1 ms 4896 KB Output is correct
36 Correct 1 ms 4896 KB Output is correct
37 Correct 1 ms 4892 KB Output is correct
38 Correct 1 ms 4880 KB Output is correct
39 Correct 1 ms 4896 KB Output is correct
40 Correct 1 ms 4892 KB Output is correct
41 Correct 1 ms 4896 KB Output is correct
42 Correct 1 ms 4884 KB Output is correct