Submission #1061380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1061380	2024-08-16T08:29:33 Z	vjudge1	Toy Train (IOI17_train)	C++17	0 / 100	5 ms	1628 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	1628 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1628 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1372 KB	Output is correct
4	Incorrect	5 ms	1628 KB	3rd lines differ - on the 13th token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-