Submission #1310020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310020		lnw143	Toy Train (IOI17_train)	C++17	37 / 100	6 ms	1852 KiB

train

#include "train.h"

#include <bits/stdc++.h>

#define rg(x) (x).begin(),(x).end()

using namespace std;

using vi=vector<int>;

const int N=5005,S=1.5e7;

int n,m;

vi e[N],ee[N];

int d[N];

int dfn[N],low[N],dfc;
int stk[N],tp,scc[N],scnt;
bool instk[N];
int bz[N],f[N],g[N];

map<int,int> dp[18];

void tarjan(int u) {
	dfn[u]=low[u]=++dfc;
	instk[u]=1;
	stk[++tp]=u;
	for(auto v : e[u])
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(instk[v])
			low[u]=min(low[u],dfn[v]);
	if(low[u]==dfn[u]) {
		++scnt;
		do instk[stk[tp]]=0,scc[stk[tp]]=scnt; while(stk[tp--]!=u);
	}
}

vi who_wins(vi a,vi r,vi u,vi v) {
	n=a.size(),m=u.size();
	const auto check1=[&]() {
		for(int i=0; i<m; ++i) if(u[i]!=v[i]&&u[i]+1!=v[i]) return 0;
		return 1;
	};
	if(check1()) {
		for(int i=0; i<m; ++i) if(u[i]==v[i]) bz[u[i]]|=1; else bz[u[i]]|=2;
		vi ans(n,0);
		for(int i=n-1; i>=0; --i) {
			if((a[i]==r[i]&&(bz[i]&1))||(~bz[i]&2)) ans[i]=r[i];
			else ans[i]=ans[i+1];
		}
		return ans;
	}
	if(count(rg(a),0)==0) {
		for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
		for(int i=0; i<n; ++i) if(!dfn[i]) tarjan(i);
		for(int i=0; i<n; ++i) {
			bz[scc[i]]|=r[i];
			for(auto j : e[i]) if(scc[i]==scc[j]) bz[scc[i]]|=2; else ee[scc[i]].push_back(scc[j]);
		}
		for(int i=1; i<=scnt; ++i) {
			f[i]=bz[i]==3;
			for(auto j : ee[i]) f[i]|=f[j];
		}
		vector<int> ans(n);
		for(int i=0; i<n; ++i) ans[i]=f[scc[i]];
		return ans;
	}
	if(count(rg(a),1)==0) {
		for(int i=0; i<m; ++i) if(r[u[i]]+r[v[i]]==0) e[u[i]].push_back(v[i]);
		for(int i=0; i<n; ++i) if(!r[i]&&!dfn[i]) tarjan(i);
		for(int i=0; i<n; ++i) if(!r[i]) {
			for(auto j : e[i]) if(scc[i]==scc[j]) bz[scc[i]]|=1;
		}
		for(int i=0; i<n; ++i) g[i]=bz[scc[i]];
		for(int i=0; i<m; ++i) if(r[u[i]]+r[v[i]]!=0) e[u[i]].push_back(v[i]);
		memset(dfn,0,sizeof(dfn));
		scnt=dfc=0;
		for(int i=0; i<n; ++i) if(!dfn[i]) tarjan(i);
		for(int i=0; i<n; ++i)
			for(auto j : e[i])
				if(scc[i]!=scc[j])
					ee[scc[i]].push_back(scc[j]);
		for(int i=0; i<n; ++i) f[scc[i]]|=g[i];
		for(int i=1; i<=scnt; ++i) for(auto j : ee[i]) f[i]|=f[j];
		vector<int> ans(n);
		for(int i=0; i<n; ++i) ans[i]=!f[scc[i]];
		return ans;
	}
	if(n<=15) {
		for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
		const auto hash=[&](const vector<int> &a) {
			int x=0;
			for(auto i : a) x=x*3+i;
			return x;
		};
		function<int(vector<int>,int)> dfs=[&](vector<int> s,int u) -> int {
			int h=hash(s);
			if(dp[u].count(h)) return dp[u][h];
			for(auto v : e[u]) {
				if(s[v]==2&&a[u]==1) return dp[u][h]=1;
				if(s[v]==1&&a[u]==0) return dp[u][h]=0;
				if(s[v]==0) {
					vector<int> t=s;
					t[v]=1;
					if(r[v]) for(auto &i : t) if(i==1) i=2;
					if(dfs(t,v)==a[u]) return dp[u][h]=a[u];
				}
			}
			return dp[u][h]=a[u]^1;
		};
		vector<int> ans(n);
		for(int i=0; i<n; ++i) {
			vector<int> x(n);
			x[i]=r[i]+1;
			ans[i]=dfs(x,i);
		}
		return ans;
	}
	return {};
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51