oj.uz

Submission #789947

# Submission time Handle Problem Language Result Execution time Memory
789947 2023-07-22T08:04:38 Z ymm Toy Train (IOI17_train) C++17
15 / 100
 2000 ms 1236 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 = 5050;
vector<int> A[N];
int col[N];
bool charg[N];
int n, m;
bool vis[N];
int height[N];

bool dfs(int v, int h, int mxc)
{
	height[v] = h;
	vis[v] = 1;
	if (charg[v])
		mxc = h;
	bool ans = col[v]? 0: 1;
	for (int u : A[v]) {
		bool wu;
		if (vis[u])
			wu = height[u] <= mxc;
		else
			wu = dfs(u, h+1, mxc);
		if (col[v])
			ans |= wu;
		else
			ans &= wu;
	}
	vis[v] = 0;
	return ans;
}

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];
		charg[i] = r[i];
	}
	Loop (i,0,m) {
		int v = V[i], u = U[i];
		A[v].push_back(u);
	}
	vector<int> ans(n);
	Loop (i,0,n) {
		ans[i] = dfs(i, 0, -1);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1228 KB Output is correct
2 Correct 53 ms 980 KB Output is correct
3 Correct 25 ms 932 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 5 ms 840 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 808 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 65 ms 424 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 24 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 11 ms 444 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 424 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1228 KB Output is correct
2 Correct 53 ms 980 KB Output is correct
3 Correct 25 ms 932 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 5 ms 840 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 808 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 428 KB Output is correct
15 Correct 65 ms 424 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 428 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 2 ms 428 KB Output is correct
20 Correct 24 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 11 ms 444 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 424 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Execution timed out 2068 ms 1108 KB Time limit exceeded
33 Halted 0 ms 0 KB -