oj.uz

Submission #798072

# Submission time Handle Problem Language Result Execution time Memory
798072 2023-07-30T10:45:43 Z LittleCube Toy Train (IOI17_train) C++17
0 / 100
 233 ms 1876 KB 
#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;

	// Check solely A
	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] && a[i] == 1)
			dfs(i);
	for (int i = 0; i < n; i++)
		vis[i] = 0;
	reverse(order.begin(), order.end());
	for (int i : order)
		if (!vis[i] && a[i] == 1)
			dfscc(i, ++k);
	for (int i = 0; i < n; i++)
		vis[i] = 0;

	vector<int> ans(n, -1);

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

	// Check B
	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]] == 0 && a[v[i]] == 0)
		{
			E[u[i]].emplace_back(v[i]);
			R[v[i]].emplace_back(u[i]);
		}

	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
					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);
			}
			if (req[i] <= 0)
				ans[i] = 0;
		}

	// check mixed
	for (int i = 0; i < n + 1; i++)
		E[i].clear(), R[i].clear();
	for (int i = 0; i < m; i++)
	{
		E[u[i]].emplace_back(v[i]);
		R[v[i]].emplace_back(u[i]);
	}

	vector<int> win(n, 0), lose(n, 0);
	queue<int> q;

	for (int j = 0; j < n; j++)
		if (ans[j] >= 0)
			q.push(j);
	for (int j = 0; j < n; j++)
		if (a[j])
			win[j] = 1, lose[j] = E[j].size();
		else
			win[j] = E[j].size(), lose[j] = 1;

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		if (ans[x] == 0)
		{
			for (auto y : R[x])
				if (--lose[y] == 0)
				{
					q.emplace(y);
					ans[y] = 0;
				}
		}
		else
		{
			for (auto y : R[x])
				if (--win[y] == 0)
				{
					q.emplace(y);
					ans[y] = 1;
				}
		}
	}
	int t = *max_element(ans.begin(), ans.end());
	for (auto &i : ans)
		if (i == -1)
			i = t ^ 1;
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1408 KB Output is correct
2 Correct 84 ms 1648 KB Output is correct
3 Correct 128 ms 1748 KB Output is correct
4 Correct 80 ms 1748 KB Output is correct
5 Correct 218 ms 1780 KB Output is correct
6 Correct 218 ms 1732 KB Output is correct
7 Correct 184 ms 1724 KB Output is correct
8 Correct 117 ms 1708 KB Output is correct
9 Correct 21 ms 1620 KB Output is correct
10 Incorrect 26 ms 1760 KB 3rd lines differ - on the 1st token, expected: '1', found: '-2'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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