Submission #430556

#	Time	Username	Problem	Language	Result	Execution time	Memory
430556		rainboy	Toy Train (IOI17_train)	C++98	38 / 100	2083 ms	105448 KiB

train

#include "train.h"
#include <stdlib.h>
 
using namespace std;
 
const int N = 5000;
 
typedef vector<int> vi;
 
int *ej[N], eo[N];
int dd[N][N + 1], out[N], n;
char rr[N];
 
void dfs(int i, int t) {
	int o;
 
	if (--dd[i][t] != 0)
		return;
	dd[i][t] = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], t_;
 
		if (t != n)
			dfs(j, t + 1);
		else if (rr[i])
			for (t_ = 1; t_ <= n; t_++)
				dfs(j, t_);
	}
}
 
vi who_wins(vi aa, vi rr_, vi uu, vi vv) {
	int m = uu.size(), h, i, j, t;
	vi ans(n = aa.size());
 
	for (i = 0; i < n; i++)
		rr[i] = rr_[i];
	for (h = 0; h < m; h++)
		out[uu[h]]++, eo[vv[h]]++;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]), eo[i] = 0;
	for (h = 0; h < m; h++)
		ej[vv[h]][eo[vv[h]]++] = uu[h];
	for (i = 0; i < n; i++) {
		dd[i][0] = !rr[i] ? 1 : 0;
		for (t = 1; t <= n; t++)
			dd[i][t] = t == n || !rr[i] ? (aa[i] ? out[i] : 1) : 0;
	}
	for (i = 0; i < n; i++)
		dfs(i, 0);
	for (i = 0; i < n; i++)
		ans[i] = dd[i][n] >= 0;
	return ans;
}

Compilation message (stderr)

train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:32:27: warning: unused variable 'j' [-Wunused-variable]
   32 |  int m = uu.size(), h, i, j, t;
      |                           ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51