oj.uz

Submission #1039486

# Submission time Handle Problem Language Result Execution time Memory
1039486 2024-07-31T00:35:01 Z juicy Amusement Park (JOI17_amusement_park) C++17
10 / 100
 18 ms 33760 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]) {
        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]][B[i]] = 1;
    G[B[i]][A[i]] = 1;
    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]) {
        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]][B[i]] = 1;
    G[B[i]][A[i]] = 1;
    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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4880 KB Output is correct
2 Correct 1 ms 4884 KB Output is correct
3 Correct 1 ms 5136 KB Output is correct
4 Correct 1 ms 4880 KB Output is correct
5 Correct 1 ms 5052 KB Output is correct
6 Correct 2 ms 4896 KB Output is correct
7 Correct 2 ms 5148 KB Output is correct
8 Correct 2 ms 5156 KB Output is correct
9 Correct 2 ms 5148 KB Output is correct
10 Correct 2 ms 4896 KB Output is correct
11 Runtime error 4 ms 5212 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 29020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4884 KB Output is correct
2 Correct 1 ms 4896 KB Output is correct
3 Correct 1 ms 4896 KB Output is correct
4 Correct 3 ms 10304 KB Output is correct
5 Correct 3 ms 10308 KB Output is correct
6 Correct 4 ms 10300 KB Output is correct
7 Correct 4 ms 10308 KB Output is correct
8 Correct 3 ms 10304 KB Output is correct
9 Correct 15 ms 33760 KB Output is correct
10 Correct 12 ms 33608 KB Output is correct
11 Correct 14 ms 33612 KB Output is correct
12 Correct 1 ms 4896 KB Output is correct
13 Correct 2 ms 4896 KB Output is correct
14 Correct 1 ms 4884 KB Output is correct
15 Correct 2 ms 4884 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 29276 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 29272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -