답안 #257495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257495	2020-08-04T10:58:05 Z	islingr	Amusement Park (JOI17_amusement_park)	C++17	64 / 100	33 ms	4368 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], out[N], timer = 0;
void init(int u) {
  in[u] = timer++;
  for (int v : g[u]) {
    g[v].erase(find(all(g[v]), u));
    p[v] = u; init(v);
  }
  out[u] = timer;
}

ll cur = 0, x = 0;
bool add(int u, ll z) {
  int s = in[u] % B;
  cur |= 1ll << s;
  x |= z << s;
	return __builtin_popcountll(cur) == B;
}
bool dfs(int u, int z) {
	if (add(u, z)) return true;
  for (int v : g[u]) {
    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);
	int u = P;
	while (u && out[P] - in[u] < B) u = p[u];
	if (B <= out[P] - in[u]) {
		while (P != u) V = Move(P[p]), P = p[P];
		dfs(P, V);
	} else assert(false);
  return x;
}

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3 ms	2288 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	3812 KB	Output is correct
2	Correct	29 ms	3812 KB	Output is correct
3	Correct	33 ms	3676 KB	Output is correct
4	Correct	18 ms	3148 KB	Output is correct
5	Correct	19 ms	3744 KB	Output is correct
6	Correct	19 ms	3620 KB	Output is correct
7	Correct	17 ms	3532 KB	Output is correct
8	Correct	18 ms	3688 KB	Output is correct
9	Correct	18 ms	3532 KB	Output is correct
10	Correct	20 ms	3364 KB	Output is correct
11	Correct	15 ms	3276 KB	Output is correct
12	Correct	18 ms	3208 KB	Output is correct
13	Correct	16 ms	3212 KB	Output is correct
14	Correct	15 ms	3012 KB	Output is correct
15	Correct	16 ms	3148 KB	Output is correct
16	Correct	17 ms	3148 KB	Output is correct
17	Correct	18 ms	3148 KB	Output is correct
18	Correct	17 ms	3396 KB	Output is correct
19	Correct	16 ms	3020 KB	Output is correct
20	Correct	15 ms	3660 KB	Output is correct
21	Correct	14 ms	3788 KB	Output is correct
22	Correct	17 ms	3428 KB	Output is correct
23	Correct	20 ms	3660 KB	Output is correct
24	Correct	20 ms	3536 KB	Output is correct
25	Correct	22 ms	3660 KB	Output is correct
26	Correct	20 ms	3660 KB	Output is correct
27	Correct	17 ms	3752 KB	Output is correct
28	Correct	17 ms	3532 KB	Output is correct
29	Correct	16 ms	3428 KB	Output is correct
30	Correct	17 ms	3396 KB	Output is correct
31	Correct	2 ms	1540 KB	Output is correct
32	Correct	2 ms	1540 KB	Output is correct
33	Correct	2 ms	1756 KB	Output is correct
34	Runtime error	3 ms	2180 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1788 KB	Output is correct
2	Correct	2 ms	1540 KB	Output is correct
3	Correct	2 ms	1784 KB	Output is correct
4	Correct	4 ms	1956 KB	Output is correct
5	Correct	4 ms	2008 KB	Output is correct
6	Correct	3 ms	2128 KB	Output is correct
7	Correct	3 ms	1956 KB	Output is correct
8	Correct	3 ms	1956 KB	Output is correct
9	Correct	13 ms	4172 KB	Output is correct
10	Correct	13 ms	4368 KB	Output is correct
11	Correct	13 ms	4172 KB	Output is correct
12	Correct	2 ms	1776 KB	Output is correct
13	Correct	2 ms	1776 KB	Output is correct
14	Correct	1 ms	1540 KB	Output is correct
15	Correct	2 ms	1668 KB	Output is correct

Subtask #4
54.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	3684 KB	Output is correct
2	Correct	27 ms	3896 KB	Output is correct
3	Correct	27 ms	3900 KB	Output is correct
4	Correct	17 ms	3408 KB	Output is correct
5	Correct	17 ms	3916 KB	Output is correct
6	Partially correct	17 ms	3864 KB	Partially correct
7	Correct	17 ms	3748 KB	Output is correct
8	Correct	16 ms	3404 KB	Output is correct
9	Correct	17 ms	3404 KB	Output is correct
10	Correct	18 ms	3276 KB	Output is correct
11	Correct	17 ms	3368 KB	Output is correct
12	Correct	15 ms	3132 KB	Output is correct
13	Correct	17 ms	3192 KB	Output is correct
14	Correct	15 ms	3176 KB	Output is correct
15	Correct	17 ms	3160 KB	Output is correct
16	Correct	17 ms	3020 KB	Output is correct
17	Correct	17 ms	3276 KB	Output is correct
18	Partially correct	19 ms	3280 KB	Partially correct
19	Correct	16 ms	3148 KB	Output is correct
20	Correct	13 ms	3832 KB	Output is correct
21	Correct	13 ms	3660 KB	Output is correct
22	Correct	19 ms	3768 KB	Output is correct
23	Correct	17 ms	3772 KB	Output is correct
24	Correct	17 ms	3660 KB	Output is correct
25	Correct	18 ms	3532 KB	Output is correct
26	Correct	17 ms	3752 KB	Output is correct
27	Correct	17 ms	3660 KB	Output is correct
28	Correct	19 ms	3424 KB	Output is correct
29	Correct	19 ms	3440 KB	Output is correct
30	Correct	19 ms	3532 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	3740 KB	Output is correct
2	Correct	27 ms	3932 KB	Output is correct
3	Correct	27 ms	3820 KB	Output is correct
4	Correct	19 ms	3404 KB	Output is correct
5	Correct	17 ms	3916 KB	Output is correct
6	Correct	20 ms	3668 KB	Output is correct
7	Correct	17 ms	3404 KB	Output is correct
8	Correct	17 ms	3584 KB	Output is correct
9	Correct	17 ms	3792 KB	Output is correct
10	Correct	15 ms	3276 KB	Output is correct
11	Correct	20 ms	3360 KB	Output is correct
12	Correct	20 ms	3208 KB	Output is correct
13	Correct	17 ms	3208 KB	Output is correct
14	Correct	26 ms	3012 KB	Output is correct
15	Correct	22 ms	3148 KB	Output is correct
16	Correct	17 ms	3020 KB	Output is correct
17	Correct	17 ms	3408 KB	Output is correct
18	Incorrect	17 ms	3020 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

답안 #257495

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 54.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
0 / 8.0

Subtask #2
0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
54.0 / 55.0

Subtask #5
0 / 17.0