답안 #282812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282812	2020-08-25T02:08:48 Z	rama_pang	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	2506 ms	11756 KB

Joi

#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])));
  }
}

Ioi

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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