Submission #676814

#	Time	Username	Problem	Language	Result	Execution time	Memory
676814		NothingXD	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	20 ms	3792 KiB

Joi

#include "Joi.h"

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

static void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
static void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e4 + 10;

static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
static vector<int> g[maxn], going;
static bool flg = false;
static int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

static void merge(int u, int v){
	int x = getdsu(u), y = getdsu(v);
	if (x == y) return;
	g[u].push_back(v);
	g[v].push_back(u);
	dsu[x] = y;
}

static void dfs(int v, int p = -1){
	sz[v] = 1;
	mxh[v] = h[v];
	par[v] = p;
	for (auto u: g[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
			sz[v] += sz[u];
			mxh[v] = max(mxh[v], mxh[u]);
		}
	}
}

static void dfs(int v, int x, int y, bool b, int p = -1){
	val[v] = y;
	going.push_back(v);
	if (x == 1) return;
	x--;
	y--;
	int bc = -1;
	for (auto u: g[v]){
		if (u != p && (bc == -1 || mxh[u] > mxh[bc])) bc = u;
	}
	int tmp = min(x, sz[bc]);
	x -= tmp;
	for (auto u: g[v]){
		if (u != p && u != bc && x != 0){
			dfs(u, min(x, sz[u]), y, false, v);
			going.push_back(v);
			y -= min(x, sz[u]);
			x -= min(x, sz[u]);
		}
	}
	dfs(bc, tmp, y, b, v);
	if (!b) going.push_back(v);
}

static void solve(){
	memset(dsu, -1, sizeof dsu);
	for (int i = 0; i < m; i++) merge(a[i], b[i]);
	dfs(0);
	int root = max_element(h, h+n) - h;
	h[root] = 0;
	dfs(root);
	int mx = max_element(h, h+n) - h;
	if (h[mx] >= 59){
		flg = true;
		return;
	}
	dfs(root, 60, 59, true);
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N;
	m = M;
  for (int i = 0; i < m; i++){
	  a[i] = A[i];
	  b[i] = B[i];
  }
  solve();
  for (int i = 0; i < n; i++){
	  if (flg) MessageBoard(i, (X >> (h[i]%60)) & 1);
	  else MessageBoard(i, (X >> val[i]) & 1);
  }
}

Ioi

#include "Ioi.h"

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

static void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
static void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e4 + 10;

static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
static vector<int> g[maxn], going;
static bool flg = false;
static int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

static void merge(int u, int v){
	int x = getdsu(u), y = getdsu(v);
	if (x == y) return;
	g[u].push_back(v);
	g[v].push_back(u);
	dsu[x] = y;
}

static void dfs(int v, int p = -1){
	sz[v] = 1;
	mxh[v] = h[v];
	par[v] = p;
	for (auto u: g[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
			sz[v] += sz[u];
			mxh[v] = max(mxh[v], mxh[u]);
		}
	}
}

static void dfs(int v, int x, int y, bool b, int p = -1){
	val[v] = y;
	going.push_back(v);
	if (x == 1) return;
	x--;
	y--;
	int bc = -1;
	for (auto u: g[v]){
		if (u != p && (bc == -1 || mxh[u] > mxh[bc])) bc = u;
	}
	int tmp = min(x, sz[bc]);
	x -= tmp;
	for (auto u: g[v]){
		if (u != p && u != bc && x != 0){
			dfs(u, min(x, sz[u]), y, false, v);
			going.push_back(v);
			y -= min(x, sz[u]);
			x -= min(x, sz[u]);
		}
	}
	dfs(bc, tmp, y, b, v);
	if (!b) going.push_back(v);
}

static void solve(){
	memset(dsu, -1, sizeof dsu);
	for (int i = 0; i < m; i++) merge(a[i], b[i]);
	dfs(0);
	int root = max_element(h, h+n) - h;
	h[root] = 0;
	dfs(root);
	int mx = max_element(h, h+n) - h;
	if (h[mx] >= 59){
		flg = true;
		return;
	}
	dfs(root, 60, 59, true);
}

static ll Calc(int v, ll x, int k = 0, int p = -1){
	ll res = (x << k);
	if (k == 59) return res;
	int bc = -1;
	for (auto u: g[v]){
		if (u != p && (bc == -1 || mxh[bc] < mxh[u])) bc = u;
	}
	return res + Calc(bc, Move(bc), k+1, v);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  n = N;
  m = M;
  for (int i = 0; i < m; i++){
	  a[i] = A[i];
	  b[i] = B[i];
  }
  solve();
  ll ans = 0;
  if (flg){
	  if (h[P] >= 59){
		  int v = P;
		  int x = V;
		  do{
			  ans += (x << (h[v] % 60));
			  if (par[v] == -1) break;
			  x = Move(par[v]);
			  v = par[v];
		  } while(h[v] % 60 != h[P]%60);
		  return ans;
	  }
	  int v = P;
	  int x = V;
	  while(par[v] != -1){
		  x = Move(par[v]);
		  v = par[v];
	  }
	  assert(v != root);
	  return Calc(v, x);
  }
  int v = P;
  ll x = V;
  while(par[v] != -1){
	  x = Move(par[v]);
	  v = par[v];
  }
  for (int i = 0; i < going.size(); i++){
	  ans |= (x << val[v]);
	  if (i + 1 != going.size()){
		  x = Move(going[i+1]);
		  v = going[i+1];
	  }
  }
  return ans;
}

Compilation message (stderr)

Joi.cpp:48:99: warning: 'root' defined but not used [-Wunused-variable]
   48 | static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
      |                                                                                                   ^~~~
Joi.cpp:30:13: warning: 'void debug_out()' defined but not used [-Wunused-function]
   30 | static void debug_out() { cerr << endl; }
      |             ^~~~~~~~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   for (int i = 0; i < going.size(); i++){
      |                   ~~^~~~~~~~~~~~~~
Ioi.cpp:164:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    if (i + 1 != going.size()){
      |        ~~~~~~^~~~~~~~~~~~~~~
Ioi.cpp: At global scope:
Ioi.cpp:30:13: warning: 'void debug_out()' defined but not used [-Wunused-function]
   30 | static void debug_out() { cerr << endl; }
      |             ^~~~~~~~~

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