oj.uz

Submission #593897

# Submission time Handle Problem Language Result Execution time Memory
593897 2022-07-11T17:21:40 Z FatihSolak Toy Train (IOI17_train) C++17
23 / 100
 1693 ms 1252 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] = -1e18;
				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] = 1e18;
				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;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:20:14: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   20 |     ndp[j] = -1e18;
      |              ^~~~~
train.cpp:27:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |     ndp[j] = 1e18;
      |              ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 674 ms 776 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 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 1231 ms 1056 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 1077 ms 924 KB Output is correct
2 Correct 1628 ms 980 KB Output is correct
3 Correct 1454 ms 1044 KB Output is correct
4 Correct 1284 ms 1032 KB Output is correct
5 Correct 1525 ms 1236 KB Output is correct
6 Correct 1602 ms 1248 KB Output is correct
7 Correct 1520 ms 1208 KB Output is correct
8 Correct 1314 ms 1192 KB Output is correct
9 Correct 1376 ms 1156 KB Output is correct
10 Correct 1386 ms 1244 KB Output is correct
11 Correct 1356 ms 1248 KB Output is correct
12 Correct 1391 ms 1252 KB Output is correct
13 Correct 1693 ms 1248 KB Output is correct
14 Correct 1534 ms 1176 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1589 ms 1036 KB Output is correct
2 Correct 1470 ms 1036 KB Output is correct
3 Correct 1514 ms 1040 KB Output is correct
4 Correct 1262 ms 984 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 648 ms 772 KB Output is correct
7 Correct 66 ms 852 KB Output is correct
8 Correct 84 ms 900 KB Output is correct
9 Correct 81 ms 852 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 104 ms 724 KB Output is correct

Subtask #6
0 / 51.0

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