oj.uz

답안 #775956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775956 2023-07-07T07:44:31 Z Jomnoi 장난감 기차 (IOI17_train) C++17
27 / 100
 1172 ms 1740 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;

const int MAX_N = 5005;
const int MAX_M = 20005;

int N, M;
bool ok;
vector <int> graph[MAX_N], rgraph[MAX_N];
int A[MAX_N], R[MAX_N], good[MAX_N];
bool visited[MAX_N];
bool self[MAX_N], nxt[MAX_N];
vector <int> ans;

bool dfs(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and dfs(v, x) == true) return true;
	}
	return false;
}

bool dfs2(int u) {
	visited[u] = true;
	if (R[u] == 1) return true;
	for (auto v : graph[u]) {
		if (visited[v] == false and dfs2(v) == true) return true;
	}
	return false;
}

bool dfs3(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and R[v] == 0 and dfs3(v, x) == true) return true;
	}
	return false;
}

void dfs4(int v) {
	visited[v] = true;
	ans[v] = 0;
	for (auto u : rgraph[v]) {
		if (visited[u] == false) dfs4(u);
	}
}

vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
	N = a.size(), M = u.size();
	bool all_1 = true, sub1 = true;
	for (int i = 0; i < N; i++) {
		A[i] = a[i], R[i] = r[i];

		if (A[i] == 0) all_1 = false;
	}
	for (int i = 0; i < M; i++) {
		if (u[i] != v[i] and u[i] != v[i] - 1) sub1 = false;
		if (u[i] == v[i]) self[u[i]] = true;
		else if (u[i] + 1 == v[i]) nxt[u[i]] = true;

		graph[u[i]].push_back(v[i]);
		rgraph[v[i]].push_back(u[i]);
	}

	ans = vector <int> (N, 0);
	if (sub1 == true) {
		ok = R[N - 1];
		for (int i = N - 1; i >= 0; i--) {
			if (self[i] == true) {
				if (R[i] == 1 and A[i] == 1) ok = true;
				else if (R[i] == 0 and A[i] == 0) ok = false;
			}
			
			ans[i] = ok;

			if (i > 0 and nxt[i - 1] == false) ok = R[i - 1];
		}
	}
	else if (all_1 == true) {
		for (int s = 0; s < N; s++) {
			if (R[s] == 0) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs(s, s) == false) R[s] = 0;
		}
		for (int s = 0; s < N; s++) {
			for (int i = 0; i < N; i++) visited[i] = false;

			ans[s] = dfs2(s);
		}
	}
	else {
		ans = vector <int> (N, 1);
		for (int s = 0; s < N; s++) {
			if (R[s] == 1) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs3(s, s) == false) continue;

			for (int i = 0; i < N; i++) visited[i] = false;
			dfs4(s);
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 468 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 1612 KB Output is correct
2 Correct 127 ms 1596 KB Output is correct
3 Correct 133 ms 1584 KB Output is correct
4 Correct 94 ms 1536 KB Output is correct
5 Correct 108 ms 1492 KB Output is correct
6 Correct 445 ms 1424 KB Output is correct
7 Correct 143 ms 1416 KB Output is correct
8 Correct 87 ms 1416 KB Output is correct
9 Correct 175 ms 1400 KB Output is correct
10 Correct 73 ms 1384 KB Output is correct
11 Correct 113 ms 1364 KB Output is correct
12 Correct 19 ms 1328 KB Output is correct
13 Correct 378 ms 1556 KB Output is correct
14 Correct 735 ms 1552 KB Output is correct
15 Correct 518 ms 1564 KB Output is correct
16 Correct 16 ms 1364 KB Output is correct
17 Correct 60 ms 1468 KB Output is correct
18 Correct 273 ms 1316 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 78 ms 1492 KB Output is correct
3 Correct 117 ms 1620 KB Output is correct
4 Correct 75 ms 1572 KB Output is correct
5 Correct 253 ms 1644 KB Output is correct
6 Correct 200 ms 1740 KB Output is correct
7 Correct 191 ms 1620 KB Output is correct
8 Correct 83 ms 1580 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 6 ms 1620 KB Output is correct
11 Correct 7 ms 1616 KB Output is correct
12 Correct 8 ms 1584 KB Output is correct
13 Correct 435 ms 1692 KB Output is correct
14 Correct 213 ms 1492 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1172 ms 1524 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 Correct 4 ms 1108 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Incorrect 0 ms 468 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -