oj.uz

Submission #282812

# Submission time Handle Problem Language Result Execution time Memory
282812 2020-08-25T02:08:48 Z rama_pang Amusement Park (JOI17_amusement_park) C++14
100 / 100
 2506 ms 11756 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int BITS = 60;

class DisjointSet {
 public:
  vector<int> p;
  vector<int> sz;
  vector<int> hist;

  DisjointSet() {}
  DisjointSet(int n) : p(n), sz(n, 1) {
    iota(begin(p), end(p), 0);
  }

  void clear() {
    for (auto i : hist) {
      p[i] = i;
      sz[i] = 1;
    }
    hist.clear();
  }

  int Unite(int x, int y) {
    hist.emplace_back(x);
    hist.emplace_back(y);
    x = Find(x), y = Find(y);
    if (x == y) return 0;
    sz[y] += sz[x];
    p[x] = y;
    return 1;
  }

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

  int Size(int x) {
    return sz[Find(x)];
  }

  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

vector<int> ord;
vector<int> vis;
vector<int> parent;
vector<vector<int>> adj;

vector<int> color;
vector<vector<int>> reach;

void Dfs(int u) {
  ord.emplace_back(u);
  vis[u] = 1;
  for (auto v : adj[u]) if (!vis[v]) {
    parent[v] = u;
    Dfs(v);
  }
}

void Init(int N, int M, vector<int> A, vector<int> B) {
  adj.resize(N);
  vis.assign(N, 0);
  parent.assign(N, -1);
  for (int i = 0; i < M; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
  }
  Dfs(0);
  reach.resize(N);
  color.assign(N, -1);
  DisjointSet D(N);
  for (int i = 1; i < BITS; i++) {
    D.Unite(parent[ord[i]], ord[i]);
  }
  for (int i = 0; i < BITS; i++) {
    if (i + 1 < BITS) {
      assert(D.SameSet(ord[i], ord[i + 1]));
    }
    color[ord[i]] = i;
    for (int j = 0; j < BITS; j++) {
      reach[ord[i]].emplace_back(ord[j]);
    }
  }
  D.clear();
  for (int i = BITS; i < N; i++) {
    int u = ord[i];
    int v = parent[u];
    static vector<int> marked(N);
    for (auto r : reach[v]) marked[r] = 1;
    for (auto exclude : reach[v]) if (exclude != v) {
      marked[exclude] = 0;
      D.Unite(u, v);
      for (auto r : reach[v]) if (marked[r]) {
        if (parent[r] != -1 && marked[parent[r]]) {
          D.Unite(r, parent[r]);
        }
      }
      if (D.Size(u) == BITS) {
        vector<int> hascolor(BITS, 0);
        reach[u].emplace_back(u);
        for (auto r : reach[v]) if (marked[r]) {
          reach[u].emplace_back(r);
          hascolor[color[r]] = 1;
        }
        assert(count(begin(hascolor), end(hascolor), 0) == 1);
        for (int i = 0; i < BITS; i++) {
          if (hascolor[i] == 0) {
            color[u] = i;
          }
        }
      }
      D.clear();
      marked[exclude] = 1;
      if (!reach[u].empty()) {
        break;
      }
    }
    for (auto r : reach[v]) marked[r] = 0;
  }

  for (int i = 0; i < N; i++) {
    assert(color[i] != -1);
    assert(reach[i].size() == BITS);
    vector<int> c(BITS);
    for (auto j : reach[i]) {
      assert(c[color[j]] == 0);
      c[color[j]] = 1;
    }
  }
}

}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  Init(N, M, vector<int>(A, A + M), vector<int>(B, B + M));
  for (int i = 0; i < N; i++) {
    MessageBoard(i, !!(X & (1ll << color[i])));
  }
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int BITS = 60;

class DisjointSet {
 public:
  vector<int> p;
  vector<int> sz;
  vector<int> hist;

  DisjointSet() {}
  DisjointSet(int n) : p(n), sz(n, 1) {
    iota(begin(p), end(p), 0);
  }

  void clear() {
    for (auto i : hist) {
      p[i] = i;
      sz[i] = 1;
    }
    hist.clear();
  }

  int Unite(int x, int y) {
    hist.emplace_back(x);
    hist.emplace_back(y);
    x = Find(x), y = Find(y);
    if (x == y) return 0;
    sz[y] += sz[x];
    p[x] = y;
    return 1;
  }

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

  int Size(int x) {
    return sz[Find(x)];
  }

  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

vector<int> ord;
vector<int> vis;
vector<int> parent;
vector<vector<int>> adj;

vector<int> color;
vector<vector<int>> reach;

void Dfs(int u) {
  ord.emplace_back(u);
  vis[u] = 1;
  for (auto v : adj[u]) if (!vis[v]) {
    parent[v] = u;
    Dfs(v);
  }
}

void Init(int N, int M, vector<int> A, vector<int> B) {
  adj.resize(N);
  vis.assign(N, 0);
  parent.assign(N, -1);
  for (int i = 0; i < M; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
  }
  Dfs(0);
  reach.resize(N);
  color.assign(N, -1);
  DisjointSet D(N);
  for (int i = 1; i < BITS; i++) {
    D.Unite(parent[ord[i]], ord[i]);
  }
  for (int i = 0; i < BITS; i++) {
    if (i + 1 < BITS) {
      assert(D.SameSet(ord[i], ord[i + 1]));
    }
    color[ord[i]] = i;
    for (int j = 0; j < BITS; j++) {
      reach[ord[i]].emplace_back(ord[j]);
    }
  }
  D.clear();
  for (int i = BITS; i < N; i++) {
    int u = ord[i];
    int v = parent[u];
    static vector<int> marked(N);
    for (auto r : reach[v]) marked[r] = 1;
    for (auto exclude : reach[v]) if (exclude != v) {
      marked[exclude] = 0;
      D.Unite(u, v);
      for (auto r : reach[v]) if (marked[r]) {
        if (parent[r] != -1 && marked[parent[r]]) {
          D.Unite(r, parent[r]);
        }
      }
      if (D.Size(u) == BITS) {
        vector<int> hascolor(BITS, 0);
        reach[u].emplace_back(u);
        for (auto r : reach[v]) if (marked[r]) {
          reach[u].emplace_back(r);
          hascolor[color[r]] = 1;
        }
        assert(count(begin(hascolor), end(hascolor), 0) == 1);
        for (int c = 0; c < BITS; c++) {
          if (hascolor[c] == 0) {
            color[u] = c;
          }
        }
      }
      D.clear();
      marked[exclude] = 1;
      if (!reach[u].empty()) {
        break;
      }
    }
    for (auto r : reach[v]) marked[r] = 0;
  }

  for (int i = 0; i < N; i++) {
    assert(color[i] != -1);
    assert(reach[i].size() == BITS);
    vector<int> c(BITS);
    for (auto j : reach[i]) {
      assert(c[color[j]] == 0);
      c[color[j]] = 1;
    }
  }
}

}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  Init(N, M, vector<int>(A, A + M), vector<int>(B, B + M));
  vector<vector<int>> tree(N);
  for (int i = 1; i < N; i++) {
    tree[parent[i]].emplace_back(i);
    tree[i].emplace_back(parent[i]);
  }
  vector<int> sub(N);
  for (auto i : reach[P]) {
    sub[i] = 1;
  }
  vector<int> path;
  function<void(int, int)> FindPath = [&](int u, int p) {
    assert(sub[u] == 1);
    path.emplace_back(u);
    for (auto v : tree[u]) if (sub[v] == 1 && v != p) {
      FindPath(v, u);
      path.emplace_back(u);
    }
  };
  FindPath(P, -1);
  assert(path.size() == 2 * BITS - 1);
  int u = P, val = V;
  long long ans = 0;
  for (auto v : path) {
    if (u != v) {
      tie(u, val) = make_pair(v, Move(v));
    }
    if (val) {
      ans |= 1ll << color[u];
    }
  }
  return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 2 ms 964 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 6 ms 904 KB Output is correct
5 Correct 6 ms 904 KB Output is correct
6 Correct 6 ms 956 KB Output is correct
7 Correct 32 ms 1040 KB Output is correct
8 Correct 4 ms 1300 KB Output is correct
9 Correct 6 ms 1296 KB Output is correct
10 Correct 2 ms 904 KB Output is correct
11 Correct 16 ms 1472 KB Output is correct
12 Correct 2 ms 1004 KB Output is correct
13 Correct 7 ms 1168 KB Output is correct
14 Correct 10 ms 1272 KB Output is correct
15 Correct 10 ms 1168 KB Output is correct
16 Correct 13 ms 1168 KB Output is correct
17 Correct 10 ms 1276 KB Output is correct
18 Correct 15 ms 1176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2477 ms 11680 KB Output is correct
2 Correct 2443 ms 11440 KB Output is correct
3 Correct 2453 ms 11484 KB Output is correct
4 Correct 473 ms 9912 KB Output is correct
5 Correct 2434 ms 10612 KB Output is correct
6 Correct 2455 ms 10456 KB Output is correct
7 Correct 2501 ms 10532 KB Output is correct
8 Correct 2355 ms 10396 KB Output is correct
9 Correct 2109 ms 10496 KB Output is correct
10 Correct 108 ms 10136 KB Output is correct
11 Correct 110 ms 10268 KB Output is correct
12 Correct 702 ms 9336 KB Output is correct
13 Correct 660 ms 9156 KB Output is correct
14 Correct 658 ms 9616 KB Output is correct
15 Correct 411 ms 9928 KB Output is correct
16 Correct 425 ms 9748 KB Output is correct
17 Correct 465 ms 10116 KB Output is correct
18 Correct 599 ms 10008 KB Output is correct
19 Correct 464 ms 9772 KB Output is correct
20 Correct 2143 ms 10284 KB Output is correct
21 Correct 2114 ms 10732 KB Output is correct
22 Correct 2440 ms 10296 KB Output is correct
23 Correct 2443 ms 10412 KB Output is correct
24 Correct 2454 ms 10332 KB Output is correct
25 Correct 2434 ms 10252 KB Output is correct
26 Correct 2425 ms 10728 KB Output is correct
27 Correct 2445 ms 10488 KB Output is correct
28 Correct 2458 ms 10732 KB Output is correct
29 Correct 2177 ms 9788 KB Output is correct
30 Correct 2285 ms 9860 KB Output is correct
31 Correct 3 ms 956 KB Output is correct
32 Correct 7 ms 952 KB Output is correct
33 Correct 4 ms 1284 KB Output is correct
34 Correct 4 ms 904 KB Output is correct
35 Correct 8 ms 776 KB Output is correct
36 Correct 4 ms 992 KB Output is correct
37 Correct 2 ms 776 KB Output is correct
38 Correct 1 ms 776 KB Output is correct
39 Correct 2 ms 904 KB Output is correct
40 Correct 6 ms 988 KB Output is correct
41 Correct 4 ms 984 KB Output is correct
42 Correct 2 ms 996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 776 KB Output is correct
3 Correct 4 ms 984 KB Output is correct
4 Correct 326 ms 2600 KB Output is correct
5 Correct 325 ms 2428 KB Output is correct
6 Correct 325 ms 2588 KB Output is correct
7 Correct 333 ms 2536 KB Output is correct
8 Correct 340 ms 2512 KB Output is correct
9 Correct 2141 ms 10808 KB Output is correct
10 Correct 2091 ms 10836 KB Output is correct
11 Correct 2093 ms 10652 KB Output is correct
12 Correct 2 ms 988 KB Output is correct
13 Correct 2 ms 904 KB Output is correct
14 Correct 2 ms 996 KB Output is correct
15 Correct 2 ms 904 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2479 ms 11464 KB Output is correct
2 Correct 2432 ms 11708 KB Output is correct
3 Correct 2409 ms 11756 KB Output is correct
4 Correct 421 ms 9916 KB Output is correct
5 Correct 2446 ms 10840 KB Output is correct
6 Correct 2218 ms 10452 KB Output is correct
7 Correct 2363 ms 10220 KB Output is correct
8 Correct 2456 ms 10112 KB Output is correct
9 Correct 2473 ms 10192 KB Output is correct
10 Correct 109 ms 10264 KB Output is correct
11 Correct 111 ms 10132 KB Output is correct
12 Correct 649 ms 9016 KB Output is correct
13 Correct 625 ms 9116 KB Output is correct
14 Correct 696 ms 9600 KB Output is correct
15 Correct 285 ms 9932 KB Output is correct
16 Correct 401 ms 9804 KB Output is correct
17 Correct 540 ms 9900 KB Output is correct
18 Correct 496 ms 9976 KB Output is correct
19 Correct 686 ms 9780 KB Output is correct
20 Correct 2179 ms 10648 KB Output is correct
21 Correct 2110 ms 10432 KB Output is correct
22 Correct 2441 ms 10436 KB Output is correct
23 Correct 2416 ms 10524 KB Output is correct
24 Correct 2418 ms 10340 KB Output is correct
25 Correct 2426 ms 10220 KB Output is correct
26 Correct 2417 ms 10584 KB Output is correct
27 Correct 2416 ms 10440 KB Output is correct
28 Correct 2497 ms 10280 KB Output is correct
29 Correct 2192 ms 9956 KB Output is correct
30 Correct 2325 ms 9832 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 11436 KB Output is correct
2 Correct 2469 ms 11564 KB Output is correct
3 Correct 2437 ms 11680 KB Output is correct
4 Correct 499 ms 9848 KB Output is correct
5 Correct 2435 ms 10704 KB Output is correct
6 Correct 2506 ms 10324 KB Output is correct
7 Correct 2417 ms 10192 KB Output is correct
8 Correct 2167 ms 10764 KB Output is correct
9 Correct 2395 ms 10640 KB Output is correct
10 Correct 110 ms 10272 KB Output is correct
11 Correct 122 ms 10132 KB Output is correct
12 Correct 683 ms 9136 KB Output is correct
13 Correct 680 ms 9240 KB Output is correct
14 Correct 757 ms 9632 KB Output is correct
15 Correct 596 ms 10108 KB Output is correct
16 Correct 326 ms 9912 KB Output is correct
17 Correct 572 ms 10040 KB Output is correct
18 Correct 570 ms 10180 KB Output is correct
19 Correct 656 ms 10036 KB Output is correct
20 Correct 2136 ms 10828 KB Output is correct
21 Correct 2104 ms 10316 KB Output is correct
22 Correct 2418 ms 10588 KB Output is correct
23 Correct 2439 ms 10480 KB Output is correct
24 Correct 2419 ms 10652 KB Output is correct
25 Correct 2414 ms 10592 KB Output is correct
26 Correct 2398 ms 10132 KB Output is correct
27 Correct 2488 ms 10584 KB Output is correct
28 Correct 2421 ms 10928 KB Output is correct
29 Correct 2183 ms 9500 KB Output is correct
30 Correct 2323 ms 10036 KB Output is correct
31 Correct 4 ms 904 KB Output is correct
32 Correct 6 ms 904 KB Output is correct
33 Correct 4 ms 1168 KB Output is correct
34 Correct 3 ms 904 KB Output is correct
35 Correct 4 ms 904 KB Output is correct
36 Correct 2 ms 904 KB Output is correct
37 Correct 2 ms 1000 KB Output is correct
38 Correct 2 ms 904 KB Output is correct
39 Correct 2 ms 1000 KB Output is correct
40 Correct 7 ms 776 KB Output is correct
41 Correct 6 ms 1140 KB Output is correct
42 Correct 1 ms 992 KB Output is correct