oj.uz

답안 #72906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72906 2018-08-27T08:14:38 Z Navick 장난감 기차 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -