oj.uz

Submission #1078012

# Submission time Handle Problem Language Result Execution time Memory
1078012 2024-08-27T11:36:55 Z Elias Toy Train (IOI17_train) C++17
11 / 100
 1184 ms 1912 KB 
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#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;
	if (chargers[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);
	}

	chargers = loopable;

	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 = true;
		}

		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++)
      |                  ~~^~~~~~~~~~
train.cpp:98:12: warning: unused variable 'i' [-Wunused-variable]
   98 |   for (int i : reachable_chargers)
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 1364 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 348 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 230 ms 1608 KB Output is correct
2 Correct 173 ms 1712 KB Output is correct
3 Correct 149 ms 1676 KB Output is correct
4 Incorrect 1065 ms 1500 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 627 ms 1408 KB Output is correct
2 Correct 131 ms 1316 KB Output is correct
3 Correct 217 ms 1468 KB Output is correct
4 Correct 279 ms 1428 KB Output is correct
5 Correct 438 ms 1440 KB Output is correct
6 Correct 347 ms 1620 KB Output is correct
7 Correct 332 ms 1400 KB Output is correct
8 Correct 249 ms 1372 KB Output is correct
9 Correct 19 ms 1368 KB Output is correct
10 Correct 870 ms 1504 KB Output is correct
11 Correct 857 ms 1628 KB Output is correct
12 Correct 871 ms 1912 KB Output is correct
13 Correct 641 ms 1492 KB Output is correct
14 Correct 330 ms 1428 KB Output is correct

Subtask #5
0 / 12.0

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