oj.uz

Submission #405705

# Submission time Handle Problem Language Result Execution time Memory
405705 2021-05-16T19:30:55 Z rqi Toy Train (IOI17_train) C++14
5 / 100
 1706 ms 1576 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 < 7505; 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 696 ms 992 KB Output is correct
2 Correct 730 ms 964 KB Output is correct
3 Correct 751 ms 904 KB Output is correct
4 Correct 727 ms 964 KB Output is correct
5 Correct 707 ms 944 KB Output is correct
6 Correct 710 ms 928 KB Output is correct
7 Correct 536 ms 932 KB Output is correct
8 Correct 506 ms 844 KB Output is correct
9 Correct 681 ms 844 KB Output is correct
10 Correct 632 ms 844 KB Output is correct
11 Correct 537 ms 868 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 460 KB Output is correct
2 Correct 92 ms 472 KB Output is correct
3 Correct 86 ms 460 KB Output is correct
4 Correct 85 ms 460 KB Output is correct
5 Correct 83 ms 460 KB Output is correct
6 Correct 85 ms 472 KB Output is correct
7 Incorrect 84 ms 460 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 1296 KB Output is correct
2 Correct 993 ms 1288 KB Output is correct
3 Correct 941 ms 1376 KB Output is correct
4 Correct 1613 ms 1300 KB Output is correct
5 Correct 1654 ms 1576 KB Output is correct
6 Correct 1388 ms 1488 KB Output is correct
7 Correct 1546 ms 1484 KB Output is correct
8 Incorrect 1170 ms 1480 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 1104 KB Output is correct
2 Incorrect 1205 ms 1180 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 Incorrect 1706 ms 1276 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 992 KB Output is correct
2 Correct 730 ms 964 KB Output is correct
3 Correct 751 ms 904 KB Output is correct
4 Correct 727 ms 964 KB Output is correct
5 Correct 707 ms 944 KB Output is correct
6 Correct 710 ms 928 KB Output is correct
7 Correct 536 ms 932 KB Output is correct
8 Correct 506 ms 844 KB Output is correct
9 Correct 681 ms 844 KB Output is correct
10 Correct 632 ms 844 KB Output is correct
11 Correct 537 ms 868 KB Output is correct
12 Correct 87 ms 460 KB Output is correct
13 Correct 92 ms 472 KB Output is correct
14 Correct 86 ms 460 KB Output is correct
15 Correct 85 ms 460 KB Output is correct
16 Correct 83 ms 460 KB Output is correct
17 Correct 85 ms 472 KB Output is correct
18 Incorrect 84 ms 460 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
19 Halted 0 ms 0 KB -