Submission #1025891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025891	2024-07-17T11:00:13 Z	parsadox2	Toy Train (IOI17_train)	C++17	11 / 100	1538 ms	1780 KB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10;

int n , m , st;
vector <int> adj[N];
bool dead[N] , marked[N] , cyc[N];
bool vis[N][2];

void Dfs(int v , int ty)
{
	vis[v][ty] = true;
	if(dead[v] && ty == 0)
	{
		Dfs(v , 1);
		return;
	}
	for(auto u : adj[v])
	{
		if(u == st && ty == 1)
			cyc[st] = true;
		if(!vis[u][ty])
			Dfs(u , ty);
	}
}

bool Solve(int v)
{
	marked[v] = true;
	if(cyc[v])
		return true;
	bool flg = false;
	for(auto u : adj[v])  if(!marked[u])
		flg |= Solve(u);
	return flg;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	vector<int> res(a.size());
	for(int i = 0 ; i < n ; i++)
		dead[i] = r[i];
	for(int i = 0 ; i < m ; i++)
		adj[u[i]].push_back(v[i]);
	for(int i = 0 ; i < n ; i++)
	{
		//cout << "DFS " << i << endl;
		st = i;
		for(int j = 0 ; j < n ; j++)
			vis[j][0] = vis[j][1] = false;
		Dfs(i , 0);
	}
	for(int i = 0 ; i < n ; i++)
	{
		memset(marked , false , sizeof marked);
		res[i] = Solve(i);
	}
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	137 ms	1304 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
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 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	1628 KB	Output is correct
2	Correct	208 ms	1624 KB	Output is correct
3	Correct	228 ms	1624 KB	Output is correct
4	Correct	1220 ms	1372 KB	Output is correct
5	Correct	1116 ms	1500 KB	Output is correct
6	Correct	779 ms	1368 KB	Output is correct
7	Correct	300 ms	1372 KB	Output is correct
8	Correct	370 ms	1392 KB	Output is correct
9	Correct	351 ms	1400 KB	Output is correct
10	Correct	406 ms	1368 KB	Output is correct
11	Correct	385 ms	1112 KB	Output is correct
12	Correct	35 ms	1112 KB	Output is correct
13	Correct	1508 ms	1624 KB	Output is correct
14	Correct	1438 ms	1624 KB	Output is correct
15	Correct	1504 ms	1780 KB	Output is correct
16	Correct	1531 ms	1588 KB	Output is correct
17	Correct	1538 ms	1640 KB	Output is correct
18	Correct	345 ms	1112 KB	Output is correct