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

train

#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;
}

Subtask #1
0 / 5.0

#	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	-

Subtask #2
0 / 10.0

#	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	-

Subtask #3
11.0 / 11.0

#	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