#527054 (C++17) No.1153 ねこちゃんゲーム

提出ソース

結果

問題	No.1153 ねこちゃんゲーム
ユーザー	chocopuu
提出日時	2020-08-09 03:11:54
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,257 bytes
コンパイル時間	2,731 ms
コンパイル使用メモリ	222,884 KB
実行使用メモリ	109,632 KB
最終ジャッジ日時	2024-10-03 04:01:10
合計ジャッジ時間	38,604 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,248 KB
testcase_02	WA	-
testcase_03	AC	5 ms 5,248 KB
testcase_04	WA	-
testcase_05	AC	5 ms 5,248 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	AC	752 ms 101,004 KB
testcase_09	WA	-
testcase_10	AC	752 ms 101,012 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	760 ms 101,008 KB
testcase_14	WA	-
testcase_15	AC	721 ms 101,012 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	751 ms 101,396 KB
testcase_19	WA	-
testcase_20	AC	718 ms 101,784 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	715 ms 101,392 KB
testcase_24	WA	-
testcase_25	AC	736 ms 101,644 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	739 ms 97,212 KB
testcase_29	WA	-
testcase_30	AC	778 ms 97,216 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	644 ms 109,132 KB
testcase_34	WA	-
testcase_35	AC	661 ms 109,100 KB
testcase_36	WA	-
testcase_37	RE	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	RE	-
testcase_41	WA	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In lambda function:
main.cpp:171:9: warning: control reaches end of non-void function [-Wreturn-type]
  171 |         };
      |         ^

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;


template <class T> class ReRooting {
public:
	int NodeCount;

public:
	std::vector<std::vector<int>> Adjacents;
	std::vector<std::vector<int>> IndexForAdjacent;

	std::vector<T> Res;
	std::vector<std::vector<T>> DP;

	T Identity;
	std::function<T(T, T)> Operate;
	std::function<T(T, int)> OperateNode;

public:
	ReRooting(int nodeCount, std::vector<std::vector<int>> edges, T identity,
				std::function<T(T, T)> operate,
				std::function<T(T, int)> operateNode) {
		NodeCount = nodeCount;

		Identity = identity;
		Operate = operate;
		OperateNode = operateNode;

		std::vector<std::vector<int>> adjacents(nodeCount);
		std::vector<std::vector<int>> indexForAdjacents(nodeCount);

		for (int i = 0; i < edges.size(); i++) {
			auto &edge = edges[i];
			indexForAdjacents[edge[0]].push_back(adjacents[edge[1]].size());
			indexForAdjacents[edge[1]].push_back(adjacents[edge[0]].size());
			adjacents[edge[0]].push_back(edge[1]);
			adjacents[edge[1]].push_back(edge[0]);
		}

		Adjacents = std::vector<std::vector<int>>(nodeCount);
		IndexForAdjacent = std::vector<std::vector<int>>(nodeCount);
		for (int i = 0; i < nodeCount; i++) {
			Adjacents[i] = adjacents[i];
			IndexForAdjacent[i] = indexForAdjacents[i];
		}

		DP = std::vector<std::vector<T>>(Adjacents.size());
		Res = std::vector<T>(Adjacents.size());

		for (int i = 0; i < Adjacents.size(); i++)
			DP[i] = std::vector<T>(Adjacents[i].size());
		if (NodeCount > 1)
			Initialize();
		else if (NodeCount == 1)
			Res[0] = OperateNode(Identity, 0);
	}

	T Query(int node) { return Res[node]; }

private:
	void Initialize() {
		std::vector<int> parents(NodeCount);
		std::vector<int> order(NodeCount);

#pragma region InitOrderedTree
		int index = 0;
		std::stack<int> stack;
		stack.push(0);
		parents[0] = -1;
		while (stack.size() > 0) {
			auto node = stack.top();
			stack.pop();
			order[index++] = node;
			for (int i = 0; i < Adjacents[node].size(); i++) {
				auto adjacent = Adjacents[node][i];
				if (adjacent == parents[node])
					continue;
				stack.push(adjacent);
				parents[adjacent] = node;
			}
		}
#pragma endregion

#pragma region fromLeaf
		for (int i = order.size() - 1; i >= 1; i--) {
			auto node = order[i];
			auto parent = parents[node];

			T accum = Identity;
			int parentIndex = -1;
			for (int j = 0; j < Adjacents[node].size(); j++) {
				if (Adjacents[node][j] == parent) {
					parentIndex = j;
					continue;
				}
				accum = Operate(accum, DP[node][j]);
			}
			DP[parent][IndexForAdjacent[node][parentIndex]] =
				OperateNode(accum, node);
		}
#pragma endregion

#pragma region toLeaf
		for (int i = 0; i < order.size(); i++) {
			auto node = order[i];
			T accum = Identity;
			std::vector<T> accumsFromTail(Adjacents[node].size());
			accumsFromTail[accumsFromTail.size() - 1] = Identity;
			for (int j = accumsFromTail.size() - 1; j >= 1; j--)
					accumsFromTail[j - 1] = Operate(DP[node][j], accumsFromTail[j]);
			for (int j = 0; j < accumsFromTail.size(); j++) {
				DP[Adjacents[node][j]][IndexForAdjacent[node][j]] =
					OperateNode(Operate(accum, accumsFromTail[j]), node);
				accum = Operate(accum, DP[node][j]);
			}
			Res[node] = OperateNode(accum, node);
		}
#pragma endregion
	}
};
/*
REP(i, N - 1) {
	int a, b;
	cin >> a >> b;
	--a; --b;
	g.push_back({a, b});
}
この形式で受け取る!
*/


signed main(){
	int N, M;
	cin >> N >> M;
	vector<int>a(M);
	REP(i, M) {
		cin >> a[i];
		--a[i];
	}
	vector<vector<int>>g;
	vector<vector<int>>edges(N);
	REP(i, N - 1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g.push_back({a, b});
		edges[a].emplace_back(b);
		edges[b].emplace_back(a);
	}
	auto merge = [](int a, int b) -> int {
		return a | b;
	};
	auto f = [](int a, int b) -> int {
		REP(i, 20) {
			if(!(a & (1ll << i))) return 1ll << i;
		}
	};
	ReRooting<int> rr(N, g, 0ll, merge, f);
	int XOR = 0;
	vector<int>grundy(N);
	REP(i, N) {
		int state = rr.Query(i);
		REP(j, 20) {
			if(state & (1ll << j)) grundy[i] = j;
		}
	}
	REP(i, M) {
		XOR ^= grundy[a[i]];
	}
	vector<int>cnt(N, -1);
	REP(i, M) cnt[a[i]] = i;
	if(XOR) {
		REP(i, N) {
			if(cnt[i] == -1) continue;
			if(XOR > grundy[i]) continue;
			int count = 0;
			for(auto e: rr.DP[i]) {
				int x = e;
				REP(j, 20) {
					if(x & (1ll << j)) {
						x = j;
						break;
					}
				}
				int next_XOR = XOR ^ grundy[i] ^ x;
				if(next_XOR == 0) {
					out(cnt[i] + 1, g[i][count] + 1);
					return 0;
				}
				++count;
			}
		}
	} else {
		out(-1, -1);
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード