Submission #1061380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061380		vjudge1	Toy Train (IOI17_train)	C++17	0 / 100	5 ms	1628 KiB

train

#include <bits/stdc++.h>
#include "train.h"
 
using namespace std;
 
const int M = 5000;

vector<int> nei[M],dd;
int vis[M],low[M],ind[M],t;
stack<int> st;
bool ch[M],cy[M];

void dfs(int u)
{
	vis[u]=1;
	low[u]=ind[u]=t++;
	st.push(u);
	for (int i:nei[u])
		if (!vis[i])
		{
			dfs(i);
			low[u]=min(low[u],low[i]);
		}
		else if(vis[i]==1)
			low[u]=min(low[u],low[i]);
	if (low[u]==ind[u])
	{
		vector<int> v;
		while (st.top()!=u)
			v.push_back(st.top()),vis[st.top()]=2,st.pop();
		v.push_back(st.top()),vis[st.top()]=2;
		st.pop();
		for (int i:v)
			if (ch[i])
			{
				if (v.size()>1 or cy[i])
					dd.push_back(i);
			}
	}
}

void dfs1(int u)
{
	vis[u]=1;
	for (int i:nei[u])
		if (!vis[i])
			dfs1(i);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n=a.size(),m=u.size();
	for (int i=0;i<n;i++)
		ch[i]=r[i];
	for (int i=0;i<m;i++)
	{
		nei[u[i]].push_back(v[i]);
		if (u[i]==v[i])
			cy[u[i]]=1;
	}
	for (int i=0;i<n;i++)
		if (!vis[i])
			dfs(i);
	for (int i=0;i<n;i++)
		vis[i]=0;
	for (int i:dd)
		if (!vis[i])
			dfs1(i);
	vector<int> ans(n);
	for (int i=0;i<n;i++)
		if (vis[i])
			ans[i]=1;
	return ans;
}

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