QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34741#4251. Gamedutinmeow#2 1ms3956kbC++2010.2kb2022-06-12 06:37:262024-05-26 00:52:50

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 00:52:50]
  • 评测
  • 测评结果:2
  • 用时:1ms
  • 内存:3956kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-12 06:37:26]
  • 提交

answer

#include "game.h"

#define NDEBUG

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

#pragma region debug

#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = next(v.begin()); i != v.end(); i++)
		os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = next(d.begin()); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
		}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = next(a.begin()); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
 cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif

#pragma endregion debug

#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 = 100;

	vector<int> C, D;

	void init_fast(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);
		dbg("_4\n", A, B, C, D);
	}

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

		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;
		dbg("_4\n", s, t, A, B, C, D);
		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;
		}
		dbg(A, B, C, D);
		return false;
	}
}

void init(int N, int K) { game::init_fast(N, K); }

int add_teleporter(int u, int v) { return game::add_teleporter_fast(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

詳細信息

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 0ms
memory: 3888kb

input:

1 1
1
893123 893123
-1

output:

0

result:

ok interaction finished.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

9 9
29
893122 893124
893121 893127
893120 893124
893123 893121
893122 893131
893125 893131
893121 893126
893123 893126
893126 893131
893123 893131
893123 893125
893123 893124
893127 893125
893120 893126
893123 893120
893121 893131
893123 893127
893122 893126
893122 893127
893127 893131
893122 893125...

output:

28

result:

ok interaction finished.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

100 100
80
893180 893071
893134 893063
893150 893091
893127 893178
893142 893177
893153 893156
893127 893137
893174 893065
893127 893070
893126 893061
893171 893089
893173 893072
893153 893058
893156 893074
893151 893068
893136 893060
893120 893083
893073 893091
893148 893163
893073 893088
893156 89...

output:

80
80
80
59

result:

ok interaction finished.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

45 45
80
893143 893167
893122 893132
893123 893140
893120 893139
893158 893167
893154 893163
893133 893137
893133 893142
893135 893137
893121 893135
893137 893149
893141 893152
893122 893167
893128 893145
893140 893167
893122 893127
893134 893142
893122 893129
893141 893156
893146 893149
893123 8931...

output:

80
49

result:

ok interaction finished.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

100 100
80
893169 893058
893132 893065
893143 893068
893153 893167
893152 893182
893138 893162
893129 893163
893146 893164
893134 893180
893142 893167
893144 893059
893132 893064
893135 893091
893164 893068
893123 893179
893126 893060
893136 893140
893179 893081
893139 893181
893120 893057
893172 89...

output:

80
80
80
42

result:

ok interaction finished.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

100 100
80
893135 893081
893170 893076
893148 893075
893134 893159
893159 893073
893170 893088
893131 893138
893121 893166
893171 893168
893127 893137
893147 893145
893062 893076
893160 893059
893063 893088
893137 893073
893123 893182
893152 893170
893141 893172
893137 893087
893167 893085
893147 89...

output:

80
80
80
37

result:

ok interaction finished.

Test #7:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

100 100
80
893062 893075
893139 893156
893137 893083
893071 893075
893072 893080
893141 893060
893126 893179
893064 893081
893167 893077
893139 893165
893056 893085
893169 893182
893062 893087
893141 893078
893062 893078
893129 893176
893065 893077
893141 893181
893152 893158
893151 893078
893157 89...

output:

80
80
80
59

result:

ok interaction finished.

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 3808kb

input:

100 10
80
893135 893150
893174 893168
893159 893149
893162 893082
893158 893129
893072 893150
893088 893079
893155 893154
893086 893126
893078 893153
893177 893138
893057 893066
893151 893089
893076 893162
893165 893164
893085 893170
893084 893128
893074 893083
893138 893148
893147 893167
893071 893...

output:

80
26

result:

wrong answer Wrong Answer [1]

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%