oj.uz

Submission #409420

# Submission time Handle Problem Language Result Execution time Memory
409420 2021-05-20T17:30:54 Z rqi Toy Train (IOI17_train) C++14
10 / 100
 2000 ms 1308 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);
	}
	int REP = 10005;
	for(int rep = 0; rep < REP; 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 > (REP/(n+1))){
			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
0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1772 ms 1116 KB Output is correct
2 Correct 1605 ms 1196 KB Output is correct
3 Incorrect 1851 ms 1304 KB 3rd lines differ - on the 108th token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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