Submission #798032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
798032	2023-07-30T09:54:13 Z	LittleCube	Toy Train (IOI17_train)	C++17	11 / 100	7 ms	2004 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

int n, m, k, vis[5005], scc[5005], self[5005];
vector<int> E[5005], R[5005];
vector<int> order;
vector<int> cc[5005];

void dfs(int u)
{
	vis[u] = 1;
	for (auto v : E[u])
		if (!vis[v])
			dfs(v);
	order.emplace_back(u);
}

void dfscc(int u, int c)
{
	vis[u] = 1;
	scc[u] = c;
	cc[c].emplace_back(u);
	for (auto v : R[u])
		if (!vis[v])
			dfscc(v, c);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	n = a.size(), m = u.size(), k = -1;
	for (int i = 0; i < n + 1; i++)
		vis[i] = 0, E[i].clear(), R[i].clear(), cc[i].clear(), self[i] = 0;
	order.clear();
	for (int i = 0; i < m; i++)
	{
		if (a[u[i]] == 1 && a[v[i]] == 1)
		{
			E[u[i]].emplace_back(v[i]);
			R[v[i]].emplace_back(u[i]);
		}
		if(u[i] == v[i])
			self[u[i]] = 1;
	}

	for (int i = 0; i < n; i++)
		if (!vis[i])
			dfs(i);
	reverse(order.begin(), order.end());
	for (int i = 0; i < n; i++)
		vis[i] = 0;
	for (int i : order)
		if (!vis[i])
			dfscc(i, ++k);

	vector<int> ans(n, 0);

	for (int i = k; i >= 0; i--)
	{
		int flag = 0;
		for (int j : cc[i])
		{
			for (int p : E[j])
				if (ans[p])
					flag = 1;
			if (r[j] == 1 && (cc[i].size() > 1 || self[j]))
				flag = 1;
		}
		if (flag)
			for (int j : cc[i])
				ans[j] = 1;
	}
	return ans;
	// vector<int>
	// 	loop(n, 0);
	// for (int i = 0; i < n; i++)
	// 	if (a[i] == 0)
	// 	{
	// 		vector<int> req(n, 0);
	// 		for (int j = 0; j < n; j++)
	// 			if (r[j])
	// 				req[j] = 1e9;
	// 			else if (a[j])
	// 				req[j] = E[j].size();
	// 			else
	// 				req[j] = 1;
	// 		queue<int> q;
	// 		q.push(i);
	// 		while (!q.empty())
	// 		{
	// 			int x = q.front();
	// 			q.pop();
	// 			for (auto y : R[x])
	// 				if (--req[y] == 0)
	// 					q.emplace(y);
	// 		}
	// 		loop[i] = req[i] <= 0;
	// 	}
	// vector<int> ans(n, 1);
	// vector<int> req(n, 0);
	// queue<int> q;

	// for (int j = 0; j < n; j++)
	// 	if (loop[j])
	// 	{
	// 		q.push(j);
	// 		req[j] = 0;
	// 	}
	// 	else if (a[j])
	// 		req[j] = E[j].size();
	// 	else
	// 		req[j] = 1;

	// while (!q.empty())
	// {
	// 	int x = q.front();
	// 	ans[x] = 0;
	// 	q.pop();
	// 	for (auto y : R[x])
	// 		if (--req[y] == 0)
	// 			q.emplace(y);
	// }
	// return ans;
}

Subtask #1
0 / 5.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1876 KB	Output is correct
2	Correct	5 ms	2004 KB	Output is correct
3	Correct	6 ms	1940 KB	Output is correct
4	Correct	6 ms	1876 KB	Output is correct
5	Correct	6 ms	1824 KB	Output is correct
6	Correct	7 ms	1824 KB	Output is correct
7	Correct	6 ms	1692 KB	Output is correct
8	Correct	6 ms	1748 KB	Output is correct
9	Correct	6 ms	1748 KB	Output is correct
10	Correct	6 ms	1748 KB	Output is correct
11	Correct	6 ms	1748 KB	Output is correct
12	Correct	6 ms	1776 KB	Output is correct
13	Correct	6 ms	1948 KB	Output is correct
14	Correct	6 ms	2004 KB	Output is correct
15	Correct	6 ms	2004 KB	Output is correct
16	Correct	6 ms	2004 KB	Output is correct
17	Correct	6 ms	1988 KB	Output is correct
18	Correct	4 ms	1524 KB	Output is correct