結果

問題 No.408 五輪ピック
コンテスト
ユーザー anta
提出日時 2017-05-07 13:54:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 111 ms / 5,000 ms
コード長 4,818 bytes
コンパイル時間 2,529 ms
コンパイル使用メモリ 185,684 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-09-14 14:42:45
合計ジャッジ時間 5,016 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target ("ssse3", "pclmul")
#include "bits/stdc++.h"
#include "wmmintrin.h"
#include "tmmintrin.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 GF64 {
	uint64_t x;
	GF64() : x(0) {}
	explicit GF64(uint64_t x) : x(x) {}

	GF64 operator+(GF64 that) const {
		return GF64(x ^ that.x);
	}
	GF64 &operator+=(GF64 that) {
		return *this = *this + that;
	}
	GF64 operator*(GF64 that) const {
		const __m128i a = _mm_cvtsi64_si128(x);
		const __m128i b = _mm_cvtsi64_si128(that.x);
		const __m128i prod = _mm_clmulepi64_si128(a, b, 0x00);
		return GF64(reduce(prod));
	}
	GF64 &operator*=(GF64 that) {
		return *this = *this * that;
	}

	static inline uint64_t reduce(const __m128i &a) {
		const __m128i r = _mm_cvtsi64_si128(27);
		const __m128i table = _mm_setr_epi8(0, 27, 54, 45, 108, 119, 90, 65, 216 - 256, 195 - 256, 238 - 256, 245 - 256, 180 - 256, 175 - 256, 130 - 256, 153 - 256);
		const __m128i z = _mm_clmulepi64_si128(a, r, 0x01);
		const __m128i y = _mm_shuffle_epi8(table, _mm_srli_si128(z, 8));
		const __m128i temp1 = _mm_xor_si128(z, a);
		return _mm_cvtsi128_si64(_mm_xor_si128(temp1, y));
	}
};

int main() {
	random_device rd;
	auto random = [&rd]() {
		auto lo = rd(), hi = rd();
		return GF64(uint64_t(hi) << 32 | lo);
	};
	using F = GF64;
	struct Edge {
		int u, v;
		GF64 value;
	};
	const int K = 4;
	//See: "Parameterized Algorithms" Ch.10.4.1
	auto solve = [K](int N, const vector<Edge> &edges, const vector<vector<F>> &y) {
		F totalSum;
		vector<F> ySum(N);
		vector<vector<F>> dp;
		rep(X, 1 << K) {
			rep(i, N) {
				F sum;
				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] += e.value * ySum[e.v];
			rep(k, K - 1) {
				for (const Edge &e : edges) if (e.v != 0) {
					auto x = dp[k][e.u];
					if (x.x != 0)
						dp[k + 1][e.v] += x * e.value * ySum[e.v];
				}
			}
			for (const Edge &e : edges) if (e.v == 0)
				totalSum += dp[K - 1][e.u] * e.value;
		}
		return totalSum.x != 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 = [solve, &y, &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], e.value });
			}
			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);
			}
		}
		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