oj.uz

Submission #790011

# Submission time Handle Problem Language Result Execution time Memory
790011 2023-07-22T09:12:48 Z ymm Toy Train (IOI17_train) C++17
0 / 100
 772 ms 7248 KB 
#include "train.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 5032;
bitset<N> berese[N], narese[N];
vector<int> A[N];
int col[N];
vector<int> chargs;
int n, m;
bool self[N];

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> V, std::vector<int> U) {
	n = a.size();
	m = V.size();
	Loop (i,0,n) {
		col[i] = a[i];
		if (r[i])
			chargs.push_back(i);
	}
	Loop (i,0,m) {
		int v = V[i], u = U[i];
		A[v].push_back(u);
	}
	Loop (i,0,n)
		narese[i].set();
	Loop (i,0,n) {
		if (col[i]) {
			for (int j : A[i])
				berese[i][j] = 1;
		} else {
			for (int j : A[i])
				narese[i][j] = 0;
		}
		if (A[i].size() == 1) {
			berese[i][A[i][0]] = 1;
			narese[i][A[i][0]] = 0;
		}
	}
	Loop (i,0,n) {
		berese[i][i] = 1;
		narese[i][i] = 0;
	}
	//	Loop (i,0,n) {
	//		Loop (j,0,n)
	//			cout << berese[i][j];
	//		cout << '\n';
	//	}
	//	Loop (i,0,n) {
	//		Loop (j,0,n)
	//			cout << narese[i][j];
	//		cout << '\n';
	//	}
	//	cout << '\n';
	Loop (k,0,n) Loop (i,0,n) {
		if (!narese[i][k]) {
			berese[i] &= berese[k];
			narese[i] &= narese[k];
		}
		if (berese[i][k]) {
			berese[i] |= berese[k];
			narese[i] |= narese[k];
		}
	}
	//	Loop (i,0,n) {
	//		Loop (j,0,n)
	//			cout << berese[i][j];
	//		cout << '\n';
	//	}
	//	Loop (i,0,n) {
	//		Loop (j,0,n)
	//			cout << narese[i][j];
	//		cout << '\n';
	//	}
	//	cout << '\n';
	//}
	Loop (i,0,n) {
		self[i] = 1;
		Loop (j,0,n)
			self[i] &= narese[i][j] || berese[j][i];
	}
	vector<int> fans(n);
	Loop (i,0,n) {
		bool ans = 0;
		for (int c : chargs)
			ans |= berese[i][c] && self[c];
		fans[i] = ans;
	}
	return fans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 6996 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 340 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 Incorrect 115 ms 7248 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 772 ms 7124 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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