Submission #257488

#	Time	Username	Problem	Language	Result	Execution time	Memory
257488		islingr	Amusement Park (JOI17_amusement_park)	C++17	80 / 100	43 ms	4924 KiB

Joi

#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, sz[N]; ll x;
void dfs_sz(int u) {
	sz[u] = 1;
	for (int v : g[u]) {
		g[v].erase(find(all(g[v]), u));
		dfs_sz(v);
		sz[u] += sz[v];
	}
	sort(all(g[u]), [&](int u, int v) { return sz[u] > sz[v]; });
}

void dfs(int u) {
	MessageBoard(u, x >> timer & 1);
	if (++timer == B) timer = 0;
	for (int v : g[u]) dfs(v);
}
}

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_sz(0); dfs(0);
}

Ioi

#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], sz[N], timer = 0;
void dfs_sz(int u) {
	sz[u] = 1;
	for (int v : g[u]) {
		g[v].erase(find(all(g[v]), u));
		dfs_sz(v);
		sz[u] += sz[v];
	}
	sort(all(g[u]), [&](int u, int v) { return sz[u] > sz[v]; });
}

void init(int u) {
  in[u] = timer++;
  for (int v : g[u]) {
    p[v] = u; init(v);
  }
}

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

  dfs_sz(0); init(0);
	while (sz[P] < B) {
    if (add(P, V)) break;
    V = Move(p[P]), P = p[P];
  }
	assert(dfs(P, V));
  return x;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 52 / 55
• Subtask 5: 0 / 17