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

提出ソース

結果

問題	No.1153 ねこちゃんゲーム
ユーザー	chocopuu
提出日時	2020-08-09 03:52:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	748 ms / 2,500 ms
コード長	5,110 bytes
コンパイル時間	2,632 ms
コンパイル使用メモリ	224,072 KB
実行使用メモリ	109,628 KB
最終ジャッジ日時	2024-10-03 04:52:13
合計ジャッジ時間	33,297 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	3 ms 6,816 KB
testcase_03	AC	3 ms 6,820 KB
testcase_04	AC	4 ms 6,816 KB
testcase_05	AC	4 ms 6,816 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	650 ms 101,588 KB
testcase_08	AC	616 ms 100,984 KB
testcase_09	AC	630 ms 101,112 KB
testcase_10	AC	676 ms 101,300 KB
testcase_11	AC	654 ms 102,092 KB
testcase_12	AC	628 ms 101,024 KB
testcase_13	AC	645 ms 101,436 KB
testcase_14	AC	636 ms 102,192 KB
testcase_15	AC	669 ms 101,212 KB
testcase_16	AC	631 ms 101,308 KB
testcase_17	AC	659 ms 101,220 KB
testcase_18	AC	630 ms 101,504 KB
testcase_19	AC	637 ms 101,580 KB
testcase_20	AC	643 ms 101,888 KB
testcase_21	AC	625 ms 102,016 KB
testcase_22	AC	640 ms 101,296 KB
testcase_23	AC	674 ms 101,780 KB
testcase_24	AC	697 ms 101,756 KB
testcase_25	AC	748 ms 102,468 KB
testcase_26	AC	685 ms 101,464 KB
testcase_27	AC	693 ms 97,132 KB
testcase_28	AC	719 ms 97,136 KB
testcase_29	AC	732 ms 98,248 KB
testcase_30	AC	724 ms 97,288 KB
testcase_31	AC	685 ms 98,172 KB
testcase_32	AC	569 ms 109,200 KB
testcase_33	AC	566 ms 109,124 KB
testcase_34	AC	616 ms 109,116 KB
testcase_35	AC	584 ms 109,276 KB
testcase_36	AC	574 ms 109,228 KB
testcase_37	AC	327 ms 107,852 KB
testcase_38	AC	277 ms 107,892 KB
testcase_39	AC	300 ms 108,096 KB
testcase_40	AC	323 ms 109,628 KB
testcase_41	AC	270 ms 109,516 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;


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

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;
			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;
				}
			}
		}
	} else {
		out(-1, -1);
	}
}

yukicoder

結果

テストケース

ソースコード