oj.uz

Submission #405704

# Submission time Handle Problem Language Result Execution time Memory
405704 2021-05-16T19:29:57 Z rqi Toy Train (IOI17_train) C++14
15 / 100
 2000 ms 1452 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;

const int MOD = 1e9+7;

#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back

void ckmin(pi& a, pi b){
	a = min(a, b);
}

void ckmax(pi& a, pi b){
	a = max(a, b);
}

const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
array<pi, mx> dp;
array<pi, mx> ndp;
int trans_ans[mx];

vi cur_ans;
void genCurAns(int node){
	assert(trans_ans[node] != -1);
	assert(cur_ans[node] > 1);
	// cout << "node: " << node << "\n";
	// for(int i = 0; i < n; i++){
	// 	cout << "cur_ans[" << i << "]: " << cur_ans[i] << "\n";
	// }
	if(cur_ans[trans_ans[node]] <= 1){
		cur_ans[node] = cur_ans[trans_ans[node]];
		return;
	}
	cur_ans[node] = 3;
	if(cur_ans[trans_ans[node]] == 2){
		genCurAns(trans_ans[node]);
		cur_ans[node] = cur_ans[trans_ans[node]];
		return;
	}
	else{
		assert(cur_ans[trans_ans[node]] == 3);
		int sum = r[node];
		int cur_node = trans_ans[node];
		while(cur_node != node){
			sum+=r[cur_node];
			cur_node = trans_ans[cur_node];
		}
		if(sum >= 1){
			cur_ans[node] = 1;
		}
		else{
			cur_ans[node] = 0;
		}
		return;
	}
}

vi getAnsFromTrans(){
	cur_ans = vi(n, 2);
	for(int i = 0; i < n; i++){
		if(cur_ans[i] == 2){
			genCurAns(i);
		}
	}
	return cur_ans;
}

vi who_wins(vi _a, vi _r, vi _u, vi _v) {
	a = _a;
	r = _r;
	u = _u;
	v = _v;
	n = sz(a);
	m = sz(u);
	for(int i = 0; i < m; i++){
		adj[u[i]].pb(v[i]);
	}

	for(int i = 0; i < n; i++){
		dp[i] = mp(0, -1);
	}
	for(int rep = 0; rep < 10005; rep++){
		for(int i = 0; i < n; i++){
			if(a[i]){
				ndp[i] = mp(-MOD, -1);
			}
			else{
				ndp[i] = mp(MOD, -1);
			}
		}
		for(int i = 0; i < n; i++){
			if(a[i]){
				for(int& u: adj[i]){
					ckmax(ndp[i], mp(dp[u].f, u));
				}
			}
			else{
				for(int& u: adj[i]){
					ckmin(ndp[i], mp(dp[u].f, u));
				}
			}
			if(r[i]){
				ndp[i].f++;
			}
		}
		swap(dp, ndp);
	}

	vi ans(n, 0);
	for(int i = 0; i < n; i++){
		if(dp[i].f > 2000){
			ans[i] = 1;
		}
	}
	return ans;
	for(int i = 0; i < n; i++){
		cout << i << " " << dp[i].f << " " << dp[i].s << "\n";
	}

	for(int i = 0; i < n; i++){
		trans_ans[i] = dp[i].s;
		cout << "i, trans[i]: " << i << " " << trans_ans[i] << "\n";
		assert(trans_ans[i] != -1);
	}
	return getAnsFromTrans();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 904 KB Output is correct
2 Correct 991 ms 900 KB Output is correct
3 Correct 999 ms 904 KB Output is correct
4 Correct 955 ms 948 KB Output is correct
5 Correct 941 ms 908 KB Output is correct
6 Correct 953 ms 896 KB Output is correct
7 Correct 725 ms 964 KB Output is correct
8 Correct 679 ms 900 KB Output is correct
9 Correct 919 ms 892 KB Output is correct
10 Correct 849 ms 888 KB Output is correct
11 Correct 707 ms 864 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 492 KB Output is correct
2 Correct 111 ms 472 KB Output is correct
3 Correct 115 ms 480 KB Output is correct
4 Correct 115 ms 580 KB Output is correct
5 Correct 112 ms 468 KB Output is correct
6 Correct 119 ms 480 KB Output is correct
7 Correct 122 ms 460 KB Output is correct
8 Correct 116 ms 476 KB Output is correct
9 Correct 113 ms 460 KB Output is correct
10 Correct 116 ms 484 KB Output is correct
11 Correct 115 ms 472 KB Output is correct
12 Correct 113 ms 488 KB Output is correct
13 Correct 113 ms 472 KB Output is correct
14 Correct 114 ms 460 KB Output is correct
15 Correct 112 ms 476 KB Output is correct
16 Correct 116 ms 460 KB Output is correct
17 Correct 113 ms 484 KB Output is correct
18 Correct 111 ms 460 KB Output is correct
19 Correct 118 ms 580 KB Output is correct
20 Correct 113 ms 460 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 1352 KB Output is correct
2 Correct 1382 ms 1284 KB Output is correct
3 Correct 1243 ms 1288 KB Output is correct
4 Execution timed out 2075 ms 1452 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 1200 KB Output is correct
2 Incorrect 1616 ms 1184 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 904 KB Output is correct
2 Correct 991 ms 900 KB Output is correct
3 Correct 999 ms 904 KB Output is correct
4 Correct 955 ms 948 KB Output is correct
5 Correct 941 ms 908 KB Output is correct
6 Correct 953 ms 896 KB Output is correct
7 Correct 725 ms 964 KB Output is correct
8 Correct 679 ms 900 KB Output is correct
9 Correct 919 ms 892 KB Output is correct
10 Correct 849 ms 888 KB Output is correct
11 Correct 707 ms 864 KB Output is correct
12 Correct 113 ms 492 KB Output is correct
13 Correct 111 ms 472 KB Output is correct
14 Correct 115 ms 480 KB Output is correct
15 Correct 115 ms 580 KB Output is correct
16 Correct 112 ms 468 KB Output is correct
17 Correct 119 ms 480 KB Output is correct
18 Correct 122 ms 460 KB Output is correct
19 Correct 116 ms 476 KB Output is correct
20 Correct 113 ms 460 KB Output is correct
21 Correct 116 ms 484 KB Output is correct
22 Correct 115 ms 472 KB Output is correct
23 Correct 113 ms 488 KB Output is correct
24 Correct 113 ms 472 KB Output is correct
25 Correct 114 ms 460 KB Output is correct
26 Correct 112 ms 476 KB Output is correct
27 Correct 116 ms 460 KB Output is correct
28 Correct 113 ms 484 KB Output is correct
29 Correct 111 ms 460 KB Output is correct
30 Correct 118 ms 580 KB Output is correct
31 Correct 113 ms 460 KB Output is correct
32 Correct 1287 ms 1352 KB Output is correct
33 Correct 1382 ms 1284 KB Output is correct
34 Correct 1243 ms 1288 KB Output is correct
35 Execution timed out 2075 ms 1452 KB Time limit exceeded
36 Halted 0 ms 0 KB -