oj.uz

Submission #72906

# Submission time Handle Problem Language Result Execution time Memory
72906 2018-08-27T08:14:38 Z Navick Toy Train (IOI17_train) C++17
11 / 100
 16 ms 1964 KB 
#include <bits/stdc++.h>
#include "train.h"

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 5e3 + 10;

bool t[maxN];
int num[maxN], c[maxN], a[maxN], sz[maxN];

vector <int> adj[maxN], rev[maxN], topol;
bool mark[maxN];

void DFS(int v)
{
	mark[v] = true;
	for (auto u : adj[v])
		if(!c[u] && !mark[u]) DFS(u);
	topol.pb(v);
}

void SFD(int v, int comp)
{
	mark[v] = true;
	sz[comp] ++;
	num[v] = comp;

	for (auto u : rev[v])
		if(!mark[u] && !c[u]) SFD(u, comp);
}

void sfd(int v)
{
	mark[v] = true;
	for (auto u : rev[v])
		if(!mark[u]) sfd(u);
}

std::vector<int> who_wins(std::vector<int> A, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = A.size(), m = u.size();
	
	for (int i=0; i<n; i++) c[i] = r[i], a[i] = A[i];

	for (int i=0; i<m; i++)
	{
		adj[u[i]].pb(v[i]);
		rev[v[i]].pb(u[i]);
	
		if(u[i] == v[i]) t[u[i]] = true;
	}

	for (int i=0; i<n; i++)
		if(!c[i] && !mark[i]) DFS(i);

	reverse(topol.begin(), topol.end());
	memset(mark, 0, sizeof mark);
	
	int id = 0;
	for (auto v : topol)
		if(!mark[v]){
			SFD(v, id);
			id ++;
		}

	memset(mark, 0, sizeof mark);
	for (int i=0; i<n; i++)
	{
		if(c[i]) continue ;
		int id = num[i];
		if(sz[id] > 1 || t[i]) sfd(i);
	}

	vector <int> ans;

	for (int i=0; i<n; i++)
		ans.pb(!mark[i]);

	return ans;

}

Subtask #1
0 / 5.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1824 KB Output is correct
2 Correct 13 ms 1872 KB Output is correct
3 Correct 12 ms 1872 KB Output is correct
4 Incorrect 15 ms 1872 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1872 KB Output is correct
2 Correct 14 ms 1872 KB Output is correct
3 Correct 13 ms 1872 KB Output is correct
4 Correct 13 ms 1872 KB Output is correct
5 Correct 14 ms 1872 KB Output is correct
6 Correct 13 ms 1872 KB Output is correct
7 Correct 13 ms 1872 KB Output is correct
8 Correct 14 ms 1872 KB Output is correct
9 Correct 14 ms 1872 KB Output is correct
10 Correct 16 ms 1872 KB Output is correct
11 Correct 14 ms 1872 KB Output is correct
12 Correct 11 ms 1872 KB Output is correct
13 Correct 12 ms 1940 KB Output is correct
14 Correct 11 ms 1940 KB Output is correct

Subtask #5
0 / 12.0

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