oj.uz

Submission #970433

# Submission time Handle Problem Language Result Execution time Memory
970433 2024-04-26T14:07:14 Z Itamar Toy Train (IOI17_train) C++14
11 / 100
 1487 ms 1624 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 < 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])if (bad[j])g = 1;
				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 529 ms 1228 KB 3rd lines differ - on the 26th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 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 266 ms 1584 KB Output is correct
2 Correct 289 ms 1576 KB Output is correct
3 Correct 270 ms 1368 KB Output is correct
4 Incorrect 308 ms 1532 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 1235 ms 1396 KB Output is correct
2 Correct 1272 ms 1436 KB Output is correct
3 Correct 273 ms 1520 KB Output is correct
4 Correct 191 ms 1624 KB Output is correct
5 Correct 1133 ms 1516 KB Output is correct
6 Correct 1375 ms 1508 KB Output is correct
7 Correct 1339 ms 1512 KB Output is correct
8 Correct 227 ms 1476 KB Output is correct
9 Correct 1320 ms 1620 KB Output is correct
10 Correct 1475 ms 1540 KB Output is correct
11 Correct 1487 ms 1548 KB Output is correct
12 Correct 1487 ms 1544 KB Output is correct
13 Correct 1227 ms 1620 KB Output is correct
14 Correct 1318 ms 1468 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 1624 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 529 ms 1228 KB 3rd lines differ - on the 26th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -