Submission #1310016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310016		lnw143	Toy Train (IOI17_train)	C++17	16 / 100	5 ms	1856 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;

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];

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;
	}
	for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
	if(count(rg(a),0)==0) {
		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;
	}
	return {};
}

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