Submission #406845

# Submission time Handle Problem Language Result Execution time Memory
406845 2021-05-18T06:07:21 Z 8e7 Toy Train (IOI17_train) C++14
11 / 100
224 ms 2216 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]; 
int group[maxn];
int ord[maxn];
int ti = 0;
void dfs(int n) {
	found[n] = 1;
	for (int v:adj[n]) {
		if (!found[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]) dfs2(v);
	}
}
bool dfs3(int n) {
	found[n] = 1;
	if (tag[n]) return true;
	bool ret = false;
	for (int v:scc[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++) {
		if (!found[i]) dfs(i);
	}
	for (int i = 0;i < n;i++) found[i] = 0;
	int cnt = 0;
	for (int i = n - 1;i >= 0;i--) {
		if (!found[ord[i]]) {
			node.clear();
			dfs2(ord[i]);
			int ans = 0;
			for (int j:node) ans |= r[j];
			if(node.size() > 1 || (node.size() == 1 && self[ord[i]]))	tag[cnt] = ans;
			for (int j:node) group[j] = cnt;
			cnt++;
		}
	}	
	for (int i = 0;i < m;i++) {
		scc[group[u[i]]].push_back(group[v[i]]);
	}
	vector<int> ret;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) found[j] = 0;
		bool res = dfs3(group[i]);
		ret.push_back(res ? 1 : 0);
	}
	return ret;
}
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1740 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 648 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 101 ms 2216 KB Output is correct
2 Correct 96 ms 2156 KB Output is correct
3 Correct 93 ms 2096 KB Output is correct
4 Correct 11 ms 1996 KB Output is correct
5 Correct 17 ms 1944 KB Output is correct
6 Correct 70 ms 1868 KB Output is correct
7 Correct 11 ms 1868 KB Output is correct
8 Correct 32 ms 1896 KB Output is correct
9 Correct 36 ms 1940 KB Output is correct
10 Correct 26 ms 1812 KB Output is correct
11 Correct 58 ms 1784 KB Output is correct
12 Correct 30 ms 1800 KB Output is correct
13 Correct 11 ms 1996 KB Output is correct
14 Correct 11 ms 1996 KB Output is correct
15 Correct 11 ms 1996 KB Output is correct
16 Correct 11 ms 1996 KB Output is correct
17 Correct 11 ms 1996 KB Output is correct
18 Correct 224 ms 1708 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1680 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1928 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1740 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -