oj.uz

Submission #576825

# Submission time Handle Problem Language Result Execution time Memory
576825 2022-06-13T15:27:03 Z dutinmeow Game (APIO22_game) C++17
2 / 100
 1 ms 208 KB 
#include "game.h"

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

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

namespace game {
	int N, K;
	vector<int> A, B;
	vector<vector<int>> G, H;

	void init_slow(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		iota(A.begin(), A.begin() + K, 0);
		B.assign(N, INT_MIN);
		iota(B.begin(), B.begin() + K, 0);
		G.resize(N);
		H.resize(N);
	}	

	bool add_teleporter_slow(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);
		
		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (dfsb(v, k))
					return true;
			return false;
		});

		return dfsa(s, A[t]) || dfsb(t, B[s]);
	}

	const int S = 700;

	vector<int> C, D;

	void init_mid(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		B.assign(N, INT_MIN);
		C.assign(N, INT_MAX);
		D.assign(N, INT_MIN);
		for (int i = 0; i < K; i++) {
			A[i] = i;
			B[i] = i;
			C[i] = i / S; 
			D[i] = i / S;
		}
		G.resize(N);
		H.resize(N);
	}

	bool add_teleporter_mid(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);

		int p = -1;

		auto dfsc = y_combinator([&](auto dfsc, int u, int k) -> bool {
			if (C[u] <= k)
				return false;
			C[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : H[u])
				if (dfsc(v, k))
					return true;
			return false;
		});

		auto dfsd = y_combinator([&](auto dfsd, int u, int k) -> bool {
			if (k <= D[u])
				return false;
			D[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : G[u])
				if (dfsd(v, k))
					return true;
			return false;
		});

		if (dfsc(s, C[t]) || dfsd(t, D[s]))
			return true;
		if (p == -1)
			return false;
		int b = C[p];

		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (C[v] == D[v] && C[v] == b && dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (C[v] == D[v] && C[v] == b && dfsb(v, k))
					return true;
			return false;
		});

		for (int i = b * S; i < min((b + 1) * S, K); i++) {
			for (int v : H[i])
				if (C[v] == D[v] && C[v] == b && dfsa(v, A[i]))
					return true;
			for (int v : G[i])
				if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
					return true;
		}
		return false;
	}

	const int LOG_N = 20;
	
	void init_fast(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		iota(A.begin(), A.begin() + K, 0);
		B.assign(N, INT_MIN);
		iota(B.begin(), B.begin() + K, 0);
		C.assign(N, LOG_N - 1);
		fill_n(C.begin(), K, 0);
		G.resize(N);
		H.resize(N);
	}	

	bool add_teleporter_fast(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);

		auto dfsa = y_combinator([&](auto dfsa, int u, int b, vector<int> &tem_vec) -> bool {
			if (K < u && A[u] <= B[u])
				return true;
			if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) {
				tem_vec.push_back(u);
				C[u] = b;
			}
			for (int v : G[u]) {
				if (C[v] <= b + 1 && A[v] / (1 << b) < A[u] / (1 << b)) {
					A[v] = A[u];
					if (dfsa(v, b, tem_vec))
						return true;
				}
			}
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int b, vector<int> &tem_vec) -> bool {
			if (K < u && A[u] <= B[u])
				return true;
			if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) {
				tem_vec.push_back(u);
				C[u] = b;
			}
			for (int v : H[u]) {
				if (C[v] <= b + 1 && B[v] / (1 << b) > B[u] / (1 << b)) {
					B[v] = B[u];
					if (dfsb(v, b, tem_vec))
						return true;
				}
			}
			return false;
		});

		vector<int> cur_vec;
		for (int b = LOG_N - 1; b >= 0; b--) {
			if (C[t] <= b && A[t] / (1 << (b - 1)) < A[s] / (1 << (b - 1)))
				cur_vec.push_back(t);
			if (C[s] <= b && B[s] / (1 << (b - 1)) > B[t] / (1 << (b - 1)))
				cur_vec.push_back(s);
			vector<int> tem_vec;
			for (int u : cur_vec) {
				for (int v : H[u])
					A[v] = max(A[v], A[u]);
				for (int v : G[u])
					B[v] = min(B[v], B[u]);
				if (dfsa(u, b - 1, tem_vec) || dfsb(u, b - 1, tem_vec))
					return true;
			}
			cur_vec = move(tem_vec);
		}
		return false;
	}
}

bool mid = true;

void init(int N, int K) { 
	if (K >= 150000)
		mid = true;
	if (mid)
		game::init_fast(N, K); 
	else 
		game::init_slow(N, K);
}

int add_teleporter(int u, int v) { 
	if (mid)
		return game::add_teleporter_fast(u, v); 
	else 
		return game::add_teleporter_slow(u, v);
}

/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int K = read_int();
  std::vector<int> u(M), v(M);
  for (int i = 0; i < M; ++i) {
    u[i] = read_int();
    v[i] = read_int();
  }

  init(N, K);
  int i;
  for (i = 0; i < M; ++i) {
    int answer = add_teleporter(u[i], v[i]);
    if (answer != 0 && answer != 1) {
      i = -1;
      break;
    } else if (answer == 1) {
      break;
    }
  }
  printf("%d\n", i);
  return 0;
}

#undef NDEBUG
*/

Compilation message

game.cpp:6: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    6 | #pragma region y_combinator
      | 
game.cpp:31: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   31 | #pragma endregion y_combinator
      | 
game.cpp: In function 'bool game::add_teleporter_mid(int, int)':
game.cpp:174:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  174 |     if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
      |     ^~
game.cpp:175:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  175 |      return true;
      |      ^~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 0 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 0 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 0 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 0 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -