結果

問題 No.1153 ねこちゃんゲーム
ユーザー chocopuuchocopuu
提出日時 2020-08-09 03:52:15
言語 C++17
(gcc 11.2.0 + boost 1.78.0)
結果
AC  
実行時間 750 ms / 2,500 ms
コード長 5,110 bytes
コンパイル時間 2,905 ms
使用メモリ 109,508 KB
最終ジャッジ日時 2022-11-26 21:58:11
合計ジャッジ時間 33,264 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1 ms
3,500 KB
testcase_01 AC 1 ms
3,548 KB
testcase_02 AC 3 ms
4,036 KB
testcase_03 AC 3 ms
3,984 KB
testcase_04 AC 3 ms
4,036 KB
testcase_05 AC 3 ms
4,056 KB
testcase_06 AC 3 ms
4,000 KB
testcase_07 AC 666 ms
101,052 KB
testcase_08 AC 670 ms
101,080 KB
testcase_09 AC 663 ms
100,996 KB
testcase_10 AC 646 ms
100,984 KB
testcase_11 AC 659 ms
100,868 KB
testcase_12 AC 677 ms
101,032 KB
testcase_13 AC 664 ms
100,884 KB
testcase_14 AC 647 ms
100,852 KB
testcase_15 AC 655 ms
101,136 KB
testcase_16 AC 669 ms
100,976 KB
testcase_17 AC 654 ms
101,068 KB
testcase_18 AC 654 ms
101,256 KB
testcase_19 AC 663 ms
101,296 KB
testcase_20 AC 672 ms
101,672 KB
testcase_21 AC 657 ms
101,664 KB
testcase_22 AC 647 ms
100,988 KB
testcase_23 AC 653 ms
101,396 KB
testcase_24 AC 655 ms
101,248 KB
testcase_25 AC 661 ms
101,620 KB
testcase_26 AC 663 ms
101,672 KB
testcase_27 AC 750 ms
97,060 KB
testcase_28 AC 654 ms
97,116 KB
testcase_29 AC 670 ms
96,948 KB
testcase_30 AC 640 ms
97,068 KB
testcase_31 AC 656 ms
97,144 KB
testcase_32 AC 580 ms
108,844 KB
testcase_33 AC 574 ms
108,852 KB
testcase_34 AC 568 ms
108,856 KB
testcase_35 AC 591 ms
108,856 KB
testcase_36 AC 572 ms
108,916 KB
testcase_37 AC 345 ms
107,852 KB
testcase_38 AC 281 ms
107,928 KB
testcase_39 AC 308 ms
107,776 KB
testcase_40 AC 335 ms
109,508 KB
testcase_41 AC 281 ms
109,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
	}
}
0