oj.uz

Submission #406880

# Submission time Handle Problem Language Result Execution time Memory
406880 2021-05-18T06:59:35 Z 8e7 Toy Train (IOI17_train) C++14
11 / 100
 1096 ms 1772 KB 
#include "train.h"
 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 5005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> adj[maxn], rev[maxn], scc[maxn];
bool found[maxn], poss[maxn], tag[maxn], b[maxn]; 
int group[maxn];
int ord[maxn];
int ti = 0;
void dfs(int n) {
	found[n] = 1;
	for (int v:adj[n]) {
		if (!found[v] && !b[v]) {
			dfs(v);
		}
	}
 
	ord[ti++] = n;
}
bool self[maxn];
vector<int> node;
void dfs2(int n) {
	node.push_back(n);
	found[n] = 1;
	for (int v:rev[n]) {
		if (!found[v] && !b[v]) dfs2(v);
	}
}
bool dfs3(int n) {
	found[n] = 1;
	if (tag[n]) return true;
	bool ret = false;
	for (int v:adj[n]) {
		if (!found[v]) ret |= dfs3(v);
	}
	return ret;
}
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 < m;i++) {
		adj[u[i]].push_back(v[i]);
		rev[v[i]].push_back(u[i]);
		if (u[i] == v[i]) self[u[i]] = 1;
	}
	for (int i = 0;i < n;i++) b[i] = r[i];
	for (int i = 0;i < n;i++) {
		if (!found[i] && !b[i]) dfs(i);
	}
	for (int i = 0;i < n;i++) found[i] = 0;
	int cnt = 0;
	for (int i = ti - 1;i >= 0;i--) {
		if (!found[ord[i]]) {
			node.clear();
			dfs2(ord[i]);
			if(node.size() > 1 || (node.size() == 1 && self[ord[i]])) {
				for (int j:node) tag[j] = 1;
			}
			for (int j:node) group[j] = cnt;
			cnt++;
		}
	}	
	vector<int> ret;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) found[j] = 0;
		bool res = dfs3(i);
		ret.push_back(res ? 0 : 1);
	}
	return ret;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1228 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 588 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 87 ms 1764 KB Output is correct
2 Correct 36 ms 1672 KB Output is correct
3 Correct 11 ms 1620 KB Output is correct
4 Incorrect 12 ms 1600 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 852 ms 1660 KB Output is correct
2 Correct 144 ms 1424 KB Output is correct
3 Correct 300 ms 1628 KB Output is correct
4 Correct 310 ms 1636 KB Output is correct
5 Correct 349 ms 1644 KB Output is correct
6 Correct 320 ms 1732 KB Output is correct
7 Correct 337 ms 1504 KB Output is correct
8 Correct 295 ms 1508 KB Output is correct
9 Correct 30 ms 1420 KB Output is correct
10 Correct 1067 ms 1656 KB Output is correct
11 Correct 1049 ms 1680 KB Output is correct
12 Correct 1096 ms 1772 KB Output is correct
13 Correct 24 ms 1624 KB Output is correct
14 Correct 38 ms 1492 KB Output is correct

Subtask #5
0 / 12.0

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