답안 #37749 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37749	2017-12-27T14:22:04 Z	funcsr	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	1322 ms	119552 KB

#include "Joi.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <functional>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  int N;
  vector<int> U, R;
  UF(int N) : N(N), U(N), R(N, 1) {
    rep(i, N) U[i] = i;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

void Joi(int N, int M, int GA[], int GB[], long long X, int T) {
  int A[10000] = {};
  vector<int> G[10000];
  int deg[10000] = {};
  set<int> S[10000], leaf[10000];
  UF uf(N);
  rep(i, M) {
    int a = GA[i], b = GB[i];
    if (!uf.same(a, b)) {
      G[a].pb(b), G[b].pb(a);
      uf.unite(a, b);
    }
  }
  rep(i, N) A[i] = -1, sort(all(G[i]));
  set<int> used, lf;
  queue<P> q;
  q.push(P(0, -1));
  rep(i, 60) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    A[x] = i;
    used.insert(x);
    if (p != -1) deg[x]++, deg[p]++;
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) if (deg[i] == 1) lf.insert(i);
  for (int x : used) S[x] = used, leaf[x] = lf;

  auto degree = [&](set<int> &S, int x) {
    int d = 0, ch = -1;
    for (int t : S) if (binary_search(all(G[t]), x)) d++, ch = t;
    return P(d, ch);
  };
  while (!q.empty()) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    S[x] = set<int>(S[p]);
    S[x].insert(x);
    leaf[x] = set<int>(leaf[p]);
    if (leaf[x].find(p) != leaf[x].end()) leaf[x].erase(p);
    assert(!leaf[x].empty());
    int from = *leaf[x].begin();
    leaf[x].erase(from);
    assert(S[x].find(from) != S[x].end());
    S[x].erase(from);
    int ch = degree(S[x], from)._2;
    int d = degree(S[x], ch)._1;
    if (d == 1) leaf[x].insert(ch);
    A[x] = A[from];
    leaf[x].insert(x);
    for (int l : leaf[x]) assert(degree(S[x], l)._1 == 1);
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) assert(S[i].size() == 60);
  rep(i, N) MessageBoard(i, (X>>A[i])&1);
}

#include "Ioi.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <functional>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  int N;
  vector<int> U, R;
  UF(int N) : N(N), U(N), R(N, 1) {
    rep(i, N) U[i] = i;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

long long Ioi(int N, int M, int GA[], int GB[], int start, int V, int T) {
  int A[10000] = {};
  vector<int> G[10000];
  int deg[10000] = {};
  set<int> S[10000], leaf[10000];
  UF uf(N);
  rep(i, M) {
    int a = GA[i], b = GB[i];
    if (!uf.same(a, b)) {
      G[a].pb(b), G[b].pb(a);
      uf.unite(a, b);
    }
  }
  rep(i, N) A[i] = -1, sort(all(G[i]));
  set<int> used, lf;
  queue<P> q;
  q.push(P(0, -1));
  rep(i, 60) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    A[x] = i;
    used.insert(x);
    if (p != -1) deg[x]++, deg[p]++;
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) if (deg[i] == 1) lf.insert(i);
  for (int x : used) S[x] = used, leaf[x] = lf;

  auto degree = [&](set<int> &S, int x) {
    int d = 0, ch = -1;
    for (int t : S) if (binary_search(all(G[t]), x)) d++, ch = t;
    return P(d, ch);
  };
  while (!q.empty()) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    S[x] = set<int>(S[p]);
    S[x].insert(x);
    leaf[x] = set<int>(leaf[p]);
    if (leaf[x].find(p) != leaf[x].end()) leaf[x].erase(p);
    assert(!leaf[x].empty());
    int from = *leaf[x].begin();
    leaf[x].erase(from);
    assert(S[x].find(from) != S[x].end());
    S[x].erase(from);
    int ch = degree(S[x], from)._2;
    int d = degree(S[x], ch)._1;
    if (d == 1) leaf[x].insert(ch);
    A[x] = A[from];
    leaf[x].insert(x);
    for (int l : leaf[x]) assert(degree(S[x], l)._1 == 1);
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) assert(S[i].size() == 60);
  bool ok[10000] = {};
  for (int t : S[start]) ok[t] = true;
  long long X = 0;
  function<void(int, int, int)> dfs = [&](int x, int p, int v) {
    X |= ((long long)v)<<A[x];
    for (int t : G[x]) if (t != p && ok[t]) {
      dfs(t, x, Move(t));
      Move(x);
    }
  };
  dfs(start, -1, V);
  return X;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7560 KB	Output is correct
2	Correct	6 ms	8352 KB	Output is correct
3	Correct	26 ms	9940 KB	Output is correct
4	Correct	3 ms	7828 KB	Output is correct
5	Correct	3 ms	7836 KB	Output is correct
6	Correct	6 ms	8360 KB	Output is correct
7	Correct	9 ms	9144 KB	Output is correct
8	Correct	18 ms	10208 KB	Output is correct
9	Correct	26 ms	9940 KB	Output is correct
10	Correct	3 ms	8348 KB	Output is correct
11	Correct	12 ms	8088 KB	Output is correct
12	Correct	0 ms	7560 KB	Output is correct
13	Correct	12 ms	9676 KB	Output is correct
14	Correct	25 ms	9672 KB	Output is correct
15	Correct	15 ms	9412 KB	Output is correct
16	Correct	12 ms	9152 KB	Output is correct
17	Correct	22 ms	9676 KB	Output is correct
18	Correct	18 ms	9408 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	518 ms	72556 KB	Output is correct
2	Correct	445 ms	68868 KB	Output is correct
3	Correct	588 ms	74136 KB	Output is correct
4	Correct	968 ms	87864 KB	Output is correct
5	Correct	345 ms	65960 KB	Output is correct
6	Correct	362 ms	66216 KB	Output is correct
7	Correct	345 ms	65960 KB	Output is correct
8	Correct	382 ms	67804 KB	Output is correct
9	Correct	436 ms	70708 KB	Output is correct
10	Correct	985 ms	119552 KB	Output is correct
11	Correct	962 ms	119552 KB	Output is correct
12	Correct	698 ms	76504 KB	Output is correct
13	Correct	718 ms	77028 KB	Output is correct
14	Correct	682 ms	79412 KB	Output is correct
15	Correct	1045 ms	106876 KB	Output is correct
16	Correct	992 ms	105556 KB	Output is correct
17	Correct	1045 ms	91832 KB	Output is correct
18	Correct	1202 ms	96840 KB	Output is correct
19	Correct	1025 ms	91560 KB	Output is correct
20	Correct	255 ms	66224 KB	Output is correct
21	Correct	225 ms	65420 KB	Output is correct
22	Correct	385 ms	66224 KB	Output is correct
23	Correct	345 ms	66228 KB	Output is correct
24	Correct	349 ms	66224 KB	Output is correct
25	Correct	362 ms	66220 KB	Output is correct
26	Correct	368 ms	66220 KB	Output is correct
27	Correct	334 ms	66228 KB	Output is correct
28	Correct	329 ms	66224 KB	Output is correct
29	Correct	338 ms	60928 KB	Output is correct
30	Correct	355 ms	63304 KB	Output is correct
31	Correct	9 ms	8360 KB	Output is correct
32	Correct	12 ms	8356 KB	Output is correct
33	Correct	15 ms	10204 KB	Output is correct
34	Correct	3 ms	8356 KB	Output is correct
35	Correct	0 ms	7560 KB	Output is correct
36	Correct	0 ms	7568 KB	Output is correct
37	Correct	0 ms	7564 KB	Output is correct
38	Correct	0 ms	7556 KB	Output is correct
39	Correct	0 ms	7564 KB	Output is correct
40	Correct	0 ms	7560 KB	Output is correct
41	Correct	0 ms	7836 KB	Output is correct
42	Correct	3 ms	7820 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7564 KB	Output is correct
2	Correct	0 ms	7560 KB	Output is correct
3	Correct	0 ms	7568 KB	Output is correct
4	Correct	28 ms	16544 KB	Output is correct
5	Correct	22 ms	16548 KB	Output is correct
6	Correct	26 ms	16540 KB	Output is correct
7	Correct	32 ms	16536 KB	Output is correct
8	Correct	32 ms	16544 KB	Output is correct
9	Correct	231 ms	65152 KB	Output is correct
10	Correct	202 ms	65156 KB	Output is correct
11	Correct	205 ms	65160 KB	Output is correct
12	Correct	0 ms	7564 KB	Output is correct
13	Correct	0 ms	7568 KB	Output is correct
14	Correct	0 ms	7296 KB	Output is correct
15	Correct	0 ms	7304 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	412 ms	69392 KB	Output is correct
2	Correct	419 ms	69656 KB	Output is correct
3	Correct	405 ms	67544 KB	Output is correct
4	Correct	899 ms	89448 KB	Output is correct
5	Correct	322 ms	65956 KB	Output is correct
6	Correct	426 ms	69648 KB	Output is correct
7	Correct	352 ms	66752 KB	Output is correct
8	Correct	359 ms	66224 KB	Output is correct
9	Correct	355 ms	66216 KB	Output is correct
10	Correct	1012 ms	119540 KB	Output is correct
11	Correct	969 ms	119548 KB	Output is correct
12	Correct	656 ms	76500 KB	Output is correct
13	Correct	652 ms	76236 KB	Output is correct
14	Correct	662 ms	78884 KB	Output is correct
15	Correct	962 ms	102120 KB	Output is correct
16	Correct	1062 ms	107676 KB	Output is correct
17	Correct	1129 ms	94464 KB	Output is correct
18	Correct	899 ms	88400 KB	Output is correct
19	Correct	1025 ms	93940 KB	Output is correct
20	Correct	255 ms	66224 KB	Output is correct
21	Correct	255 ms	65424 KB	Output is correct
22	Correct	346 ms	66224 KB	Output is correct
23	Correct	352 ms	66224 KB	Output is correct
24	Correct	362 ms	66220 KB	Output is correct
25	Correct	335 ms	66224 KB	Output is correct
26	Correct	349 ms	66224 KB	Output is correct
27	Correct	334 ms	66224 KB	Output is correct
28	Correct	328 ms	66220 KB	Output is correct
29	Correct	289 ms	60932 KB	Output is correct
30	Correct	328 ms	63316 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	386 ms	67544 KB	Output is correct
2	Correct	408 ms	68072 KB	Output is correct
3	Correct	562 ms	73616 KB	Output is correct
4	Correct	949 ms	91040 KB	Output is correct
5	Correct	332 ms	65960 KB	Output is correct
6	Correct	382 ms	66216 KB	Output is correct
7	Correct	355 ms	66220 KB	Output is correct
8	Correct	436 ms	70712 KB	Output is correct
9	Correct	345 ms	66216 KB	Output is correct
10	Correct	985 ms	119552 KB	Output is correct
11	Correct	955 ms	119544 KB	Output is correct
12	Correct	696 ms	77024 KB	Output is correct
13	Correct	668 ms	74912 KB	Output is correct
14	Correct	702 ms	80204 KB	Output is correct
15	Correct	1105 ms	92092 KB	Output is correct
16	Correct	982 ms	101864 KB	Output is correct
17	Correct	1322 ms	99224 KB	Output is correct
18	Correct	1214 ms	98164 KB	Output is correct
19	Correct	1069 ms	95264 KB	Output is correct
20	Correct	228 ms	66224 KB	Output is correct
21	Correct	219 ms	65428 KB	Output is correct
22	Correct	345 ms	66220 KB	Output is correct
23	Correct	362 ms	66228 KB	Output is correct
24	Correct	341 ms	66224 KB	Output is correct
25	Correct	322 ms	66220 KB	Output is correct
26	Correct	386 ms	66224 KB	Output is correct
27	Correct	322 ms	66228 KB	Output is correct
28	Correct	365 ms	66228 KB	Output is correct
29	Correct	312 ms	60924 KB	Output is correct
30	Correct	341 ms	63308 KB	Output is correct
31	Correct	3 ms	8356 KB	Output is correct
32	Correct	9 ms	8356 KB	Output is correct
33	Correct	18 ms	10208 KB	Output is correct
34	Correct	3 ms	8352 KB	Output is correct
35	Correct	3 ms	7564 KB	Output is correct
36	Correct	0 ms	7568 KB	Output is correct
37	Correct	0 ms	7564 KB	Output is correct
38	Correct	0 ms	7564 KB	Output is correct
39	Correct	0 ms	7564 KB	Output is correct
40	Correct	0 ms	7832 KB	Output is correct
41	Correct	6 ms	7824 KB	Output is correct
42	Correct	3 ms	7828 KB	Output is correct

답안 #37749

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0