結果

問題 No.408 五輪ピック
コンテスト
ユーザー anta
提出日時 2017-05-07 15:00:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 5,000 ms
コード長 4,571 bytes
コンパイル時間 1,877 ms
コンパイル使用メモリ 179,660 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2024-09-14 14:42:50
合計ジャッジ時間 4,081 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

struct GFLookup {
	static const int Deg = 16;
	using Word = uint16_t;
	enum : uint32_t {
		Poly = 0x1002d,
		Mask = 0x10000,
		Order = 0xffff,
	};

	array<Word, 1 << Deg> pow, log;

	GFLookup() {
		uint32_t a = 1;
		for (uint32_t i = 0; i < Order; ++ i) {
			pow[i] = (Word)a;
			log[a] = (Word)i;
			a <<= 1;
			if (a & Mask) a ^= Poly;
		}
	}

	Word mul(Word x, Word y) const {
		if (x == 0 || y == 0)
			return 0;
		uint32_t k = (uint32_t)log[x] + log[y];
		if (k >= Order) k -= Order;
		return pow[k];
	}
};


int main() {
	random_device rd;
	using F = uint16_t;
	auto random = [&rd]() {
		return uint16_t(rd() & (GFLookup::Mask - 1));
	};
	struct Edge {
		int u, v;
		F value;
	};
	GFLookup gf;
	const int K = 4;
	//See: "Parameterized Algorithms" Ch.10.4.1
	auto solve = [&gf, K](int N, const vector<Edge> &edges, const vector<vector<F>> &y) {
		F totalSum = 0;
		vector<F> ySum(N);
		vector<vector<F>> dp;
		rep(X, 1 << K) {
			rep(i, N) {
				F sum = 0;
				rep(k, K) if (X >> k & 1)
					sum ^= y[i][k];
				ySum[i] = sum;
			}
			dp.assign(K, vector<F>(N));
			for (const Edge &e : edges) if(e.u == 0 && e.v != 0)
				dp[0][e.v] ^= gf.mul(e.value, ySum[e.v]);
			rep(k, K - 1) {
				for (const Edge &e : edges) if (e.v != 0) {
					F x = dp[k][e.u];
					if (x != 0)
						dp[k + 1][e.v] ^= gf.mul(gf.mul(x, e.value), ySum[e.v]);
				}
			}
			for (const Edge &e : edges) if (e.v == 0)
				totalSum ^= gf.mul(dp[K - 1][e.u], e.value);
		}
		return totalSum != 0;
	};
	int N; int M;
	while (~scanf("%d%d", &N, &M)) {
		vector<Edge> edges(M * 2);
		for (int i = 0; i < M; ++ i) {
			int u, v;
			scanf("%d%d", &u, &v), -- u, -- v;
			edges[i * 2 + 0] = { u, v, random() };
			edges[i * 2 + 1] = { v, u, random() };
		}
		vector<vector<F>> y(N, vector<F>(K));
		rep(i, N) rep(k, K)
			y[i][k] = random();
		bool ans = solve(N, edges, y);
		if (!ans) {
			puts("NO");
			continue;
		}
		puts("YES");
#if 0
		//実際の解の構成
		//"Fast Witness Extraction Using a Decision Oracle" <https://arxiv.org/abs/1508.03572>
		vector<int> U(edges.size());
		vector<bool> tmpVis(edges.size());
		vector<Edge> tmpEdges;
		vector<int> id(N, -1);
		auto checkAndCut = [random, solve, K, &id, &edges, &U, &tmpVis, &tmpEdges](const vector<int> &A) {
			for (int i : A) tmpVis[i] = true;
			int N = 0;
			id[0] = N ++;
			for (int i : U) if (!tmpVis[i]) {
				const Edge &e = edges[i];
				if (id[e.u] == -1) id[e.u] = N ++;
				if (id[e.v] == -1) id[e.v] = N ++;
				tmpEdges.push_back(Edge{ id[e.u], id[e.v], random() });
			}
			vector<vector<F>> y(N, vector<F>(K));
			rep(i, N) rep(k, K)
				y[i][k] = random();
			bool result = solve(N, tmpEdges, y);
			for (int i : U) if (!tmpVis[i]) {
				const Edge &e = edges[i];
				id[e.u] = id[e.v] = -1;
			}
			id[0] = -1;
			if (result)
				U.erase(remove_if(U.begin(), U.end(), [&](int i) { return tmpVis[i]; }), U.end());
			for (int i : A) tmpVis[i] = false;
			tmpEdges.clear();
			return result;
		};
		iota(U.begin(), U.end(), 0);
		vector<int> W;
		queue<vector<int>> Q;
		Q.push(U);
		while (!Q.empty()) {
			vector<int> A = Q.front();
			Q.pop();
			if (A.size() == 1) {
				W.push_back(A[0]);
				continue;
			}
			vector<int> A1(A.begin(), A.begin() + A.size() / 2);
			vector<int> A2(A.begin() + A.size() / 2, A.end());
			if (checkAndCut(A1)) {
				Q.push(A2);
			} else if(checkAndCut(A2)) {
				Q.push(A1);
			} else {
				Q.push(A1);
				Q.push(A2);
			}
		}
		U = W;
		while ((int)W.size() > K + 1) {
			if (checkAndCut(vector<int>{W.back()}))
				W.pop_back();
			else
				rotate(W.begin(), W.begin() + 1, W.end());
		}
		assert(W.size() == K + 1);
		vector<int> next(N, -1);
		for (int i : W) {
			auto e = edges[i];
			assert(next[e.u] == -1);
			next[e.u] = e.v;
		}
		vector<int> cycle = { 0 };
		{
			int u = 0;
			rep(k, K) {
				u = next[u];
				cycle.push_back(u);
				assert(u != -1);
			}
			assert(next[u] == 0);
		}
		/*
		for (int u : cycle)
			cerr << u + 1 << ' ';
		cerr << endl;
		*/
#endif
	}
	return 0;
}
0