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

提出ソース

結果

問題	No.1153 ねこちゃんゲーム
ユーザー	chocopuu
提出日時	2020-08-09 03:43:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	738 ms / 2,500 ms
コード長	5,310 bytes
コンパイル時間	2,830 ms
コンパイル使用メモリ	223,640 KB
実行使用メモリ	110,736 KB
最終ジャッジ日時	2024-10-03 04:42:02
合計ジャッジ時間	32,901 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	3 ms 6,816 KB
testcase_02	AC	3 ms 6,820 KB
testcase_03	AC	3 ms 6,820 KB
testcase_04	AC	4 ms 6,820 KB
testcase_05	AC	4 ms 6,820 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	738 ms 101,076 KB
testcase_08	AC	643 ms 101,820 KB
testcase_09	AC	614 ms 101,232 KB
testcase_10	AC	637 ms 102,160 KB
testcase_11	AC	629 ms 101,096 KB
testcase_12	AC	647 ms 101,052 KB
testcase_13	AC	637 ms 101,140 KB
testcase_14	AC	600 ms 101,988 KB
testcase_15	AC	664 ms 101,040 KB
testcase_16	AC	662 ms 101,696 KB
testcase_17	AC	685 ms 101,336 KB
testcase_18	AC	627 ms 101,792 KB
testcase_19	AC	653 ms 101,956 KB
testcase_20	AC	648 ms 102,504 KB
testcase_21	AC	652 ms 102,548 KB
testcase_22	AC	607 ms 101,328 KB
testcase_23	AC	646 ms 101,400 KB
testcase_24	AC	665 ms 102,204 KB
testcase_25	AC	659 ms 101,552 KB
testcase_26	AC	644 ms 102,812 KB
testcase_27	AC	657 ms 97,632 KB
testcase_28	AC	606 ms 97,236 KB
testcase_29	AC	647 ms 97,624 KB
testcase_30	AC	641 ms 98,328 KB
testcase_31	AC	649 ms 98,184 KB
testcase_32	AC	541 ms 109,084 KB
testcase_33	AC	558 ms 109,292 KB
testcase_34	AC	569 ms 109,332 KB
testcase_35	AC	556 ms 110,248 KB
testcase_36	AC	542 ms 109,232 KB
testcase_37	AC	338 ms 107,964 KB
testcase_38	AC	269 ms 108,568 KB
testcase_39	AC	296 ms 107,964 KB
testcase_40	AC	322 ms 110,084 KB
testcase_41	AC	267 ms 110,736 KB

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

ソースコード

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;
		}
		return 0;
	};
	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(grundy[i] <= (grundy[i] ^ XOR)) continue;
			int count = 0;
			REP(j, rr.Adjacents[i].size()) {
				int x = rr.DP[i][j];
				REP(k, 20) {
					if(x & (1ll << k)) {
						x = k;
						break;
					}
				}
				int next_XOR = XOR ^ grundy[i] ^ x;
				if(next_XOR == 0) {
					out(cnt[i] + 1, rr.Adjacents[i][j] + 1);
					return 0;
				}
				++count;
			}
		}
	} else {
		out(-1, -1);
	}
}

yukicoder

結果

テストケース

ソースコード