oj.uz

Submission #257393

# Submission time Handle Problem Language Result Execution time Memory
257393 2020-08-04T08:16:22 Z islingr Amusement Park (JOI17_amusement_park) C++17
10 / 100
 33 ms 4936 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)

using ll = long long;

namespace {
const int N = 1 << 14, B = 60;
int nxt[N];
int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
  u = head(u); v = head(v);
  if (u == v) return 0;
  nxt[u] = v; return 1;
}

vector<int> g[N]; int timer = 0; ll x;
void dfs(int u, int p) {
  MessageBoard(u, x >> timer & 1);
  ++timer; if (timer == B) timer = 0;
  for (int v : g[u]) if (v != p) dfs(v, u);
}
}

void Joi(int n, int m, int a[], int b[], ll X, int t) {
  rep(u, 0, n) nxt[u] = u;
  rep(e, 0, m) {
    if (unite(a[e], b[e])) {
      g[a[e]].push_back(b[e]);
      g[b[e]].push_back(a[e]);
    }
  }
  x = X; dfs(0, -1);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)

using ll = int64_t;

namespace {
const int N = 1 << 14, B = 60;
int nxt[N];
int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
  u = head(u); v = head(v);
  if (u == v) return 0;
  nxt[u] = v; return 1;
}

vector<int> g[N];
int p[N], in[N], out[N], timer = 0;
void init(int u, int p) {
  in[u] = timer++ % B;
  for (int v : g[u]) if (v != p) init(v, u);
}

int cntr = 0;
ll U = (1ll << B) - 1, cur = 0, x = 0;
bool dfs(int u, int p, ll z) {
  cur |= 1ll << in[u];
  x |= z << in[u];
  if (cur == U) return true;
  for (int v : g[u]) {
    if (v == p) continue;
    assert(++cntr <= 2 * B);
    if (dfs(v, u, Move(v))) return true;
    Move(u);
  }
  return false;
}
}

long long Ioi(int n, int m, int a[], int b[], int P, int V, int T) {
  rep(u, 0, n) nxt[u] = u;
  rep(e, 0, m) {
    if (unite(a[e], b[e])) {
      g[a[e]].push_back(b[e]);
      g[b[e]].push_back(a[e]);
    }
  }
  init(0, -1);
  dfs(P, -1, V);
  return x;
}

Compilation message

Ioi.cpp:21:18: warning: '{anonymous}::out' defined but not used [-Wunused-variable]
 int p[N], in[N], out[N], timer = 0;
                  ^~~
Ioi.cpp:21:5: warning: '{anonymous}::p' defined but not used [-Wunused-variable]
 int p[N], in[N], out[N], timer = 0;
     ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1788 KB Output is correct
2 Correct 2 ms 1784 KB Output is correct
3 Runtime error 3 ms 2188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3896 KB Output is correct
2 Correct 27 ms 3900 KB Output is correct
3 Correct 27 ms 3684 KB Output is correct
4 Correct 17 ms 3148 KB Output is correct
5 Correct 17 ms 3592 KB Output is correct
6 Correct 17 ms 3532 KB Output is correct
7 Runtime error 18 ms 4936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1668 KB Output is correct
2 Correct 2 ms 1540 KB Output is correct
3 Correct 2 ms 1668 KB Output is correct
4 Correct 4 ms 1956 KB Output is correct
5 Correct 4 ms 2004 KB Output is correct
6 Correct 3 ms 1956 KB Output is correct
7 Correct 4 ms 2000 KB Output is correct
8 Correct 3 ms 1828 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 15 ms 4116 KB Output is correct
11 Correct 14 ms 4044 KB Output is correct
12 Correct 2 ms 1780 KB Output is correct
13 Correct 2 ms 1540 KB Output is correct
14 Correct 2 ms 1668 KB Output is correct
15 Correct 2 ms 1780 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 3812 KB Partially correct
2 Correct 29 ms 3896 KB Output is correct
3 Partially correct 27 ms 3684 KB Partially correct
4 Correct 18 ms 3408 KB Output is correct
5 Partially correct 17 ms 3660 KB Partially correct
6 Runtime error 19 ms 4892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3904 KB Output is correct
2 Incorrect 27 ms 3684 KB Output isn't correct
3 Halted 0 ms 0 KB -