【Codeforces 781D】Axel and Marston in Bitland

相关链接

题目传送门：http://codeforces.com/contest/781/problem/D

解题报告

话说这个题，你看他的路径定义多么奇怪
构造方式就是倍增嘛！

那我们也来倍增吧！
于是搞一个bitset记录哪些点可以到达就可以辣！
时间复杂度：$O(\frac{n^3 \log 10^{18}}{64})$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 501;
const int M = N * N;
const LL INF = 1000000000 * 1000000000ll;

bitset<N> f[60][N][2],ans,pre; 
int n,m;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		f[0][u][read()][v] = 1; 
	}
	for (int s=0;s<59;s++) {
		for (int i=1;i<=n;i++) {
			for (int t=0;t<=1;t++) {
				for (int j=1;j<=n;j++) {
					if (f[s][i][t][j]) {
						f[s+1][i][t] |= f[s][j][t^1];
					}
				}
			}
		}
	}
	ans[1] = 1; LL vout = 0;
	for (int s=59,t=0;~s;s--) {
		pre = ans; ans.reset();
		for (int i=1;i<=n;i++) 
			if (pre[i]) ans |= f[s][i][t];
		if (ans.count()) {
			vout += 1ll << s;
			t ^= 1; 
		} else ans = pre;
	} 
	printf("%lld\n",vout>INF?-1:vout);
	return 0;
}