oj.uz

Submission #98878

# Submission time Handle Problem Language Result Execution time Memory
98878 2019-02-27T04:39:46 Z square1001 Toy Train (IOI17_train) C++14
23 / 100
 1035 ms 1272 KB 
#include "train.h"
#include <iostream>
using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size(), m = u.size();
	vector<vector<int> > g(n);
	for(int i = 0; i < m; ++i) {
		g[u[i]].push_back(v[i]);
	}
	vector<int> dp(n, n);
	for(int i = 0; i < 2 * n; ++i) {
		vector<int> ndp(n);
		for(int j = 0; j < n; ++j) {
			if(a[j] == 1) {
				ndp[j] = 0;
				for(int k : g[j]) {
					ndp[j] = max(ndp[j], dp[k] - 1);
				}
			}
			else {
				ndp[j] = n;
				for(int k : g[j]) {
					ndp[j] = min(ndp[j], dp[k] - 1);
				}
				if(ndp[j] < 0) ndp[j] = 0;
			}
			if(r[j] == 1 && ndp[j] > 0) {
				ndp[j] = n;
			}
		}
		dp = ndp;
	}
	vector<int> ans(n);
	for(int i = 0; i < n; ++i) {
		ans[i] = (dp[i] > 0 ? 1 : 0);
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 888 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 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 617 ms 1140 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 809 ms 1016 KB Output is correct
2 Correct 787 ms 1060 KB Output is correct
3 Correct 823 ms 1272 KB Output is correct
4 Correct 1025 ms 1244 KB Output is correct
5 Correct 920 ms 1144 KB Output is correct
6 Correct 951 ms 1144 KB Output is correct
7 Correct 934 ms 1144 KB Output is correct
8 Correct 724 ms 1144 KB Output is correct
9 Correct 926 ms 1024 KB Output is correct
10 Correct 971 ms 1272 KB Output is correct
11 Correct 1025 ms 1144 KB Output is correct
12 Correct 1035 ms 1144 KB Output is correct
13 Correct 957 ms 1144 KB Output is correct
14 Correct 761 ms 1144 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 1152 KB Output is correct
2 Correct 924 ms 1144 KB Output is correct
3 Correct 882 ms 1144 KB Output is correct
4 Correct 796 ms 1148 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 513 ms 888 KB Output is correct
7 Correct 38 ms 768 KB Output is correct
8 Correct 48 ms 896 KB Output is correct
9 Correct 50 ms 884 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 51 ms 896 KB Output is correct

Subtask #6
0 / 51.0

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