oj.uz

Submission #593902

# Submission time Handle Problem Language Result Execution time Memory
593902 2022-07-11T17:23:50 Z FatihSolak Toy Train (IOI17_train) C++17
23 / 100
 1587 ms 1068 KB 
#include "train.h"
#include <bits/stdc++.h>
#define N 5005
using namespace std;
int dp[N];
int ndp[N];
vector<int> adj[N];
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size();
	int m = u.size();
	for(int i = 0;i<n;i++){
		dp[i] = n;
	}
	for(int i = 0;i<m;i++){
		adj[u[i]].push_back(v[i]);
	}
	for(int i=0;i<4*n;i++){
		for(int j = 0;j<n;j++){
			if(a[j]){
				ndp[j] = -1e9;
				for(auto u:adj[j]){
					ndp[j] = max(ndp[j],dp[u] + r[j]*n - 1);
				}
				ndp[j] = min(ndp[j],n);
			}
			else{
				ndp[j] = 1e9;
				for(auto u:adj[j]){
					ndp[j] = min(ndp[j],dp[u] + r[j]*n - 1);
				}
				if(ndp[j] <= 0){
					ndp[j] = -1e9;
				}
			}
		}
		for(int j = 0;j<n;j++){
			dp[j] = ndp[j];
		}
	}
	vector<int> res(n);
	for(int i = 0; i < n; i++){
		res[i] = (dp[i] >= 0);
	}
	return res;
}

Subtask #1
0 / 5.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1065 ms 1068 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 1097 ms 928 KB Output is correct
2 Correct 1473 ms 976 KB Output is correct
3 Correct 1285 ms 1036 KB Output is correct
4 Correct 1408 ms 1032 KB Output is correct
5 Correct 1587 ms 1024 KB Output is correct
6 Correct 1539 ms 1024 KB Output is correct
7 Correct 1580 ms 1012 KB Output is correct
8 Correct 1290 ms 1000 KB Output is correct
9 Correct 1366 ms 988 KB Output is correct
10 Correct 1289 ms 1048 KB Output is correct
11 Correct 1212 ms 1044 KB Output is correct
12 Correct 1219 ms 1040 KB Output is correct
13 Correct 1387 ms 1040 KB Output is correct
14 Correct 1404 ms 984 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 1048 KB Output is correct
2 Correct 1258 ms 1040 KB Output is correct
3 Correct 1415 ms 1036 KB Output is correct
4 Correct 1240 ms 984 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 564 ms 768 KB Output is correct
7 Correct 71 ms 852 KB Output is correct
8 Correct 69 ms 900 KB Output is correct
9 Correct 64 ms 852 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 98 ms 724 KB Output is correct

Subtask #6
0 / 51.0

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