Submission #790004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790004	2023-07-22T08:56:23 Z	Sohsoh84	Toy Train (IOI17_train)	C++17	11 / 100	279 ms	52488 KB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int n, m, col[MAXN], c;
bool A[MAXN], R[MAXN];
vector<int> adj[MAXN], adj_r[MAXN];
bool W[MAXN], in_edge[MAXN], WC[MAXN];

vector<int> ord;

void dfs(int v) {
	col[v] = 1;
	for (int u : adj[v])
		if (!col[u])
			dfs(u);

	ord.push_back(v);
}

void sfd(int v) {
	col[v] = c;
	for (int u : adj_r[v])
		if (!col[u])
			sfd(u);
}

vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u_, vector<int> v_) {
	n = a_.size();
	for (int i = 0; i < n; i++)
		A[i] = a_[i], R[i] = r_[i];
	
	m = u_.size();
	for (int i = 0; i < m; i++)
		adj[u_[i]].push_back(v_[i]), adj_r[v_[i]].push_back(u_[i]);
	
	for (int i = 0; i < n; i++)
		if (!col[i])
			dfs(i);	

	
	memset(col, 0, sizeof col);
	reverse(all(ord));
	for (int e : ord) {
		if (!col[e]) {
			c++;
			sfd(e);
		}
	}

	for (int u = 0; u < n; u++)
		for (int v : adj[u])
			if (col[u] == col[v])
				in_edge[col[u]] = true;

	for (int u = 0; u < n; u++)
		if (in_edge[col[u]] && R[u])
			WC[col[u]] = true;

	for (int i = 0; i < n; i++)
		for (int v = 0; v < n; v++)
			for (int u : adj[v])
				WC[col[v]] |= WC[col[u]];

	vector<int> res;
	for (int i = 0; i < n; i++)
		res.push_back(WC[col[i]]);
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	83 ms	51924 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	24 ms	51212 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	155 ms	52248 KB	Output is correct
2	Correct	164 ms	52228 KB	Output is correct
3	Correct	157 ms	52196 KB	Output is correct
4	Correct	245 ms	52184 KB	Output is correct
5	Correct	222 ms	52368 KB	Output is correct
6	Correct	227 ms	52292 KB	Output is correct
7	Correct	253 ms	52300 KB	Output is correct
8	Correct	252 ms	52292 KB	Output is correct
9	Correct	216 ms	52280 KB	Output is correct
10	Correct	248 ms	52240 KB	Output is correct
11	Correct	243 ms	52172 KB	Output is correct
12	Correct	234 ms	52176 KB	Output is correct
13	Correct	276 ms	52424 KB	Output is correct
14	Correct	274 ms	52420 KB	Output is correct
15	Correct	279 ms	52488 KB	Output is correct
16	Correct	274 ms	52416 KB	Output is correct
17	Correct	273 ms	52344 KB	Output is correct
18	Correct	108 ms	51900 KB	Output is correct