oj.uz

Submission #257419

# Submission time Handle Problem Language Result Execution time Memory
257419 2020-08-04T08:56:23 Z islingr Amusement Park (JOI17_amusement_park) C++17
65 / 100
 41 ms 4188 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);
  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 = 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 p[N], in[N], timer = 0;
void init(int u) {
  in[u] = timer;
  if (++timer == B) timer = 0;
  for (int v : g[u]) {
    g[v].erase(find(all(g[v]), u));
    p[v] = u;
    init(v);
  }
}

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

ll 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); while (!dfs(P, V)) V = Move(p[P]), P = p[P];
  return x;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1784 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3652 KB Output is correct
2 Correct 41 ms 3684 KB Output is correct
3 Correct 32 ms 4172 KB Output is correct
4 Correct 18 ms 3244 KB Output is correct
5 Correct 23 ms 3756 KB Output is correct
6 Correct 25 ms 3664 KB Output is correct
7 Correct 24 ms 3560 KB Output is correct
8 Correct 23 ms 3628 KB Output is correct
9 Correct 18 ms 3756 KB Output is correct
10 Correct 20 ms 3628 KB Output is correct
11 Correct 20 ms 3376 KB Output is correct
12 Correct 17 ms 3200 KB Output is correct
13 Correct 22 ms 3340 KB Output is correct
14 Correct 16 ms 3360 KB Output is correct
15 Correct 27 ms 3244 KB Output is correct
16 Correct 26 ms 3372 KB Output is correct
17 Correct 27 ms 3244 KB Output is correct
18 Correct 20 ms 3428 KB Output is correct
19 Correct 22 ms 3404 KB Output is correct
20 Correct 15 ms 3952 KB Output is correct
21 Correct 14 ms 3756 KB Output is correct
22 Incorrect 17 ms 3628 KB Wrong Answer [7]
23 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3652 KB Output is correct
2 Correct 27 ms 3684 KB Output is correct
3 Correct 27 ms 4160 KB Output is correct
4 Correct 16 ms 3244 KB Output is correct
5 Correct 17 ms 4116 KB Output is correct
6 Correct 19 ms 3768 KB Output is correct
7 Correct 17 ms 3864 KB Output is correct
8 Correct 17 ms 3700 KB Output is correct
9 Correct 18 ms 3500 KB Output is correct
10 Correct 15 ms 3632 KB Output is correct
11 Correct 16 ms 3504 KB Output is correct
12 Correct 15 ms 3336 KB Output is correct
13 Correct 15 ms 3220 KB Output is correct
14 Correct 16 ms 3436 KB Output is correct
15 Correct 17 ms 3500 KB Output is correct
16 Correct 18 ms 3412 KB Output is correct
17 Correct 16 ms 3244 KB Output is correct
18 Correct 19 ms 3408 KB Output is correct
19 Correct 22 ms 3372 KB Output is correct
20 Correct 13 ms 3756 KB Output is correct
21 Correct 13 ms 3756 KB Output is correct
22 Correct 17 ms 3628 KB Output is correct
23 Correct 18 ms 3644 KB Output is correct
24 Correct 22 ms 3652 KB Output is correct
25 Correct 16 ms 3628 KB Output is correct
26 Correct 22 ms 3888 KB Output is correct
27 Correct 17 ms 3848 KB Output is correct
28 Correct 18 ms 3500 KB Output is correct
29 Correct 17 ms 3572 KB Output is correct
30 Correct 15 ms 3488 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3908 KB Output is correct
2 Correct 27 ms 3912 KB Output is correct
3 Correct 28 ms 4160 KB Output is correct
4 Correct 19 ms 3244 KB Output is correct
5 Correct 17 ms 4188 KB Output is correct
6 Correct 17 ms 3516 KB Output is correct
7 Correct 17 ms 3688 KB Output is correct
8 Correct 17 ms 3904 KB Output is correct
9 Correct 30 ms 3900 KB Output is correct
10 Correct 15 ms 3392 KB Output is correct
11 Correct 24 ms 3392 KB Output is correct
12 Correct 17 ms 3236 KB Output is correct
13 Correct 15 ms 3236 KB Output is correct
14 Correct 17 ms 3260 KB Output is correct
15 Correct 22 ms 3364 KB Output is correct
16 Correct 17 ms 3260 KB Output is correct
17 Correct 23 ms 3260 KB Output is correct
18 Correct 17 ms 3388 KB Output is correct
19 Correct 19 ms 3260 KB Output is correct
20 Correct 15 ms 3900 KB Output is correct
21 Correct 13 ms 3860 KB Output is correct
22 Correct 18 ms 3772 KB Output is correct
23 Correct 18 ms 3644 KB Output is correct
24 Correct 18 ms 3516 KB Output is correct
25 Correct 18 ms 3904 KB Output is correct
26 Correct 19 ms 3644 KB Output is correct
27 Correct 20 ms 3772 KB Output is correct
28 Correct 19 ms 3772 KB Output is correct
29 Correct 15 ms 3624 KB Output is correct
30 Correct 20 ms 3660 KB Output is correct
31 Correct 2 ms 1672 KB Output is correct
32 Correct 2 ms 1772 KB Output is correct
33 Correct 2 ms 1680 KB Output is correct
34 Correct 2 ms 1544 KB Output is correct
35 Correct 2 ms 1772 KB Output is correct
36 Correct 3 ms 1544 KB Output is correct
37 Incorrect 2 ms 1788 KB Wrong Answer [7]
38 Halted 0 ms 0 KB -