oj.uz

Submission #1025622

# Submission time Handle Problem Language Result Execution time Memory
1025622 2024-07-17T08:15:27 Z AmirAli_H1 Toy Train (IOI17_train) C++17
11 / 100
 609 ms 13692 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "train.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 7;

int n, m;
vector<int> adj[maxn], adjr[maxn];
pii A[maxn]; int D[maxn];
int mark[maxn]; queue<int> qu;
vector<int> res;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> ux, vector<int> vx) {
	n = len(a); m = len(ux);
	for (int i = 0; i < n; i++) A[i] = Mp(a[i], r[i]);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adjr[v].pb(u);
	}
	
	res.resize(n); fill(all(res), 1);
	for (int v = 0; v < n; v++) {
		if (A[v].S != 0) continue;
		fill(mark, mark + n, 0);
		for (int i = 0; i < n; i++) {
			D[i] = len(adj[i]);
		}
		mark[v] = 1; qu.push(v);
		while (!qu.empty()) {
			int v = qu.front(); qu.pop();
			for (int u : adjr[v]) {
				D[u]--;
				if (A[u].S != 0) continue;
				if (!mark[u]) {
					if (A[u].F == 0) {
						qu.push(u); mark[u] = 1;
					}
					else if (D[u] == 0) {
						qu.push(u); mark[u] = 1;
					}
				}
			}
		}
		if (A[v].F == 1 && D[v] != 0) continue;
		if (A[v].F == 0 && D[v] == len(adj[v])) continue;
		
		for (int i = 0; i < n; i++) {
			D[i] = len(adj[i]);
			if (mark[i]) {
				qu.push(i);
			}
		}
		while (!qu.empty()) {
			int v = qu.front(); qu.pop();
			for (int u : adjr[v]) {
				D[u]--;
				if (!mark[u]) {
					if (A[u].F == 0) {
						qu.push(u); mark[u] = 1;
					}
					else if (D[u] == 0) {
						qu.push(u); mark[u] = 1;
					}
				}
			}
		}
		
		for (int i = 0; i < n; i++) res[i] &= !mark[i];
	}
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 13144 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 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12736 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Incorrect 2 ms 12636 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13404 KB Output is correct
2 Correct 96 ms 13548 KB Output is correct
3 Correct 124 ms 13400 KB Output is correct
4 Correct 112 ms 13648 KB Output is correct
5 Correct 272 ms 13652 KB Output is correct
6 Correct 283 ms 13404 KB Output is correct
7 Correct 243 ms 13608 KB Output is correct
8 Correct 108 ms 13480 KB Output is correct
9 Correct 8 ms 13400 KB Output is correct
10 Correct 10 ms 13660 KB Output is correct
11 Correct 8 ms 13660 KB Output is correct
12 Correct 16 ms 13656 KB Output is correct
13 Correct 471 ms 13640 KB Output is correct
14 Correct 256 ms 13400 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 13648 KB Output is correct
2 Correct 25 ms 13648 KB Output is correct
3 Correct 177 ms 13632 KB Output is correct
4 Correct 30 ms 13400 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Incorrect 25 ms 13288 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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