Submission #1077995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077995	2024-08-27T11:28:16 Z	Elias	Toy Train (IOI17_train)	C++17	11 / 100	1192 ms	1644 KB

train

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v);
#else
#include "train.h"
#endif

vector<vector<int>> adj;

vector<int> visited;
vector<int> reachable_chargers;

vector<int> chargers;

vector<int> loop;

void dfs_find_chargers(int i)
{
	if (visited[i])
		return;
	visited[i] = true;
	if (chargers[i])
		reachable_chargers.push_back(i);

	for (int c : adj[i])
	{
		if (visited[c])
			continue;
		dfs_find_chargers(c);
	}
}

bool dfs_find_loop(int i, int start)
{
	if (visited[i])
		return 0;
	visited[i] = true;
	bool any = false;
	for (int c : adj[i])
	{
		if (c == start)
			return true;
		if (visited[c])
			continue;
		any |= dfs_find_loop(c, start);
		if (any)
			break;
	}
	return any;
}

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();
	chargers = r;
	adj.resize(n);
	for (int i = 0; i < u.size(); i++)
	{
		adj[u[i]].push_back(v[i]);
	}

	vector<int> output;

	vector<int> loopable(n);

	for (int i = 0; i < n; i++) {
		if (loopable[i]) continue;

		visited = vector<int>(n);
		loop.clear();

		loopable[i] = dfs_find_loop(i, i);
	}

	for (int q = 0; q < n; q++)
	{
		visited = vector<int>(n);
		reachable_chargers.clear();

		dfs_find_chargers(q);

		bool any = false;

		for (int i : reachable_chargers)
		{
			any |= loopable[i];
		}

		output.push_back(any);
	}
	return output;
}

#ifdef _DEBUG

using namespace std;

int main()
{
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> a(n), r(n), u(m), v(m);

	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &a[i]));

	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));

	for (int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	vector<int> res = who_wins(a, r, u, v);

	for (int i = 0; i < (int)res.size(); i++)
		printf(i ? " %d" : "%d", res[i]);
	printf("\n");

	return 0;
}

#endif

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	279 ms	1308 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	0 ms	344 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	298 ms	1332 KB	Output is correct
2	Correct	261 ms	1364 KB	Output is correct
3	Correct	265 ms	1364 KB	Output is correct
4	Correct	1151 ms	1364 KB	Output is correct
5	Correct	905 ms	1456 KB	Output is correct
6	Correct	679 ms	1372 KB	Output is correct
7	Correct	556 ms	1404 KB	Output is correct
8	Correct	360 ms	1412 KB	Output is correct
9	Correct	344 ms	1368 KB	Output is correct
10	Correct	452 ms	1616 KB	Output is correct
11	Correct	338 ms	1360 KB	Output is correct
12	Correct	26 ms	1360 KB	Output is correct
13	Correct	1155 ms	1620 KB	Output is correct
14	Correct	1116 ms	1484 KB	Output is correct
15	Correct	1192 ms	1504 KB	Output is correct
16	Correct	1163 ms	1480 KB	Output is correct
17	Correct	1169 ms	1644 KB	Output is correct
18	Correct	356 ms	1360 KB	Output is correct