oj.uz

Submission #970450

# Submission time Handle Problem Language Result Execution time Memory
970450 2024-04-26T14:36:40 Z Itamar Toy Train (IOI17_train) C++14
0 / 100
 1331 ms 1876 KB 
#include "train.h"
#include <vector>
using namespace std;
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#include <algorithm>
#define x first
#define y second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vb vector<bool>
int n, m;
const int siz = 5e3 + 1;
vi fr[siz];
vi invf[siz];
#include <queue>
int a[siz];
int deg[siz];
void func(vi& bad) {
	vector<bool> vis(n);
	queue<int> q;
	for (int i = 0; i < n; i++)if (bad[i])q.push(i);
	for (int i = 0; i < n; i++)deg[i] = fr[i].size();
	while (!q.empty()) {
		int i = q.front();
		q.pop();
		if (vis[i])continue;
		vis[i] = 1;
		bad[i] = 1;
		for (int f : invf[i]) {
			if (vis[f])continue;
			deg[f]--;
			if (a[f] == 1) {
				if (deg[f] == fr[f].size() - 1)q.push(f);
			}
			else {
				if (deg[f] == 0)q.push(f);
			}
		}
	}
}

vi who_wins(vi A, vi R, vi U, vi V) {
	n = R.size(), m = U.size();
	for (int i = 0; i < n; i++)a[i] = A[i];
	for (int i = 0; i < m; i++) {
		fr[U[i]].push_back(V[i]);
		invf[V[i]].push_back(U[i]);
	}
	vi bad(n,1);
	for (int it = 0; it <= n; it++) {
		vi badt(n);
		/*for (int i = 0; i < n; i++) {
			//if (bad[i]) {
			if (A[i]) {
				bool g = 0;
				for (int j : fr[i])g |= bad[j];
				if (g == 0)badt[i] = 0;
				else badt[i] = 1;
			}
			else {
				for (int j : fr[i]) {
					if (bad[j] == 0) {
						badt[i] = 0;
						break;
					}
					if (j == fr[i].back())badt[i] = 1;
				}
			}
			//}
		}*/
		//bad = badt;

		vi badtt = R; for (int i = 0; i < n; i++)if (bad[i] == 0)badtt[i] = 0;
		func(badtt);
		for (int i = 0; i < n; i++)if (badtt[i] == 0)bad[i] = 0;
		
	}
	return bad;
}

Compilation message

train.cpp: In function 'void func(std::vector<int>&)':
train.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if (deg[f] == fr[f].size() - 1)q.push(f);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 1240 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 600 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 497 ms 1620 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 857 ms 1400 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 1548 KB Output is correct
2 Correct 1331 ms 1760 KB Output is correct
3 Correct 1169 ms 1748 KB Output is correct
4 Correct 1204 ms 1876 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Incorrect 116 ms 1268 KB 3rd lines differ - on the 3730th token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 1240 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -