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

提出ソース

結果

問題	No.1153 ねこちゃんゲーム
ユーザー	chocopuu
提出日時	2020-08-09 03:43:21
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	881 ms / 2,500 ms
コード長	5,310 bytes
コンパイル時間	2,787 ms
コンパイル使用メモリ	218,560 KB
実行使用メモリ	110,748 KB
最終ジャッジ日時	2024-04-14 07:29:42
合計ジャッジ時間	41,589 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	3 ms 6,812 KB
testcase_02	AC	5 ms 6,944 KB
testcase_03	AC	5 ms 6,940 KB
testcase_04	AC	5 ms 6,940 KB
testcase_05	AC	5 ms 6,944 KB
testcase_06	AC	4 ms 6,944 KB
testcase_07	AC	845 ms 101,184 KB
testcase_08	AC	831 ms 101,172 KB
testcase_09	AC	827 ms 101,176 KB
testcase_10	AC	836 ms 101,756 KB
testcase_11	AC	821 ms 101,076 KB
testcase_12	AC	821 ms 101,084 KB
testcase_13	AC	814 ms 101,592 KB
testcase_14	AC	814 ms 101,220 KB
testcase_15	AC	815 ms 101,148 KB
testcase_16	AC	808 ms 101,404 KB
testcase_17	AC	813 ms 101,292 KB
testcase_18	AC	812 ms 101,392 KB
testcase_19	AC	806 ms 101,376 KB
testcase_20	AC	881 ms 101,852 KB
testcase_21	AC	824 ms 102,528 KB
testcase_22	AC	801 ms 101,316 KB
testcase_23	AC	811 ms 102,384 KB
testcase_24	AC	803 ms 101,476 KB
testcase_25	AC	813 ms 102,384 KB
testcase_26	AC	812 ms 102,008 KB
testcase_27	AC	833 ms 97,404 KB
testcase_28	AC	836 ms 97,140 KB
testcase_29	AC	841 ms 97,664 KB
testcase_30	AC	840 ms 97,192 KB
testcase_31	AC	837 ms 97,244 KB
testcase_32	AC	703 ms 109,852 KB
testcase_33	AC	692 ms 109,768 KB
testcase_34	AC	690 ms 109,212 KB
testcase_35	AC	691 ms 110,316 KB
testcase_36	AC	678 ms 110,208 KB
testcase_37	AC	376 ms 108,384 KB
testcase_38	AC	307 ms 107,800 KB
testcase_39	AC	339 ms 108,032 KB
testcase_40	AC	367 ms 109,664 KB
testcase_41	AC	301 ms 110,748 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

結果

テストケース

ソースコード