Submission #113488

#	Time	Username	Problem	Language	Result	Execution time	Memory
113488		E869120	Toy Train (IOI17_train)	C++14	38 / 100	1349 ms	217308 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = (1 << 30);

int N, M;
int A[20009], R[20009], U[20009], V[20009];
bool u1[20009], u2[20009];

vector<int> solve_subtask1() {
	for (int i = 0; i < M; i++) {
		if (V[i] - U[i] == 0) u1[U[i]] = true;
		if (V[i] - U[i] == 1) u2[U[i]] = true;
	}
	vector<int>ans;
	for (int i = 0; i < N; i++) {
		bool arezou = false;
		for (int j = i; j < N; j++) {
			if (u1[j] == true && A[j] == 1 && R[j] == 1) { arezou = true; break; }
			if (u1[j] == true && A[j] == 0 && R[j] == 0) { break; }
			if (u2[j] == false) {
				if (R[j] == 1) arezou = true;
				break;
			}
		}
		ans.push_back((int)arezou);
	}
	return ans;
}

int dp[11009][5009]; vector<int> X[5009];

void init() {
	for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) dp[i][j] = INF; X[i].clear(); A[i] = 0; R[i] = 0; U[i] = 0; V[i] = 0; u1[i] = false; u2[i] = false; }
}

vector<int> solve_subtask2() {
	for (int i = 0; i < M; i++) X[U[i]].push_back(V[i]);
	
	int S = min(2 * N * N, 11000);
	for (int i = 0; i < N; i++) dp[S + 1][i] = 0;
	for (int i = S; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			if (R[j] == 1) {
				int cnt = 0;
				for (int k = 0; k < X[j].size(); k++) { if (dp[i + 1][X[j][k]] == INF) cnt++; }
				dp[i][j] = 0;
				if (A[j] == 1 && cnt == (int)X[j].size()) dp[i][j] = INF;
				if (A[j] == 0 && cnt >= 1) dp[i][j] = INF;
				continue;
			}
			if (A[j] == 1) {
				dp[i][j] = INF;
				for (int k = 0; k < X[j].size(); k++) {
					if (j == X[j][k]) continue;
					dp[i][j] = min(dp[i][j], dp[i + 1][X[j][k]] + 1);
				}
				if (dp[i][j] >= N + 1) dp[i][j] = INF;
			}
			else {
				dp[i][j] = 0;
				for (int k = 0; k < X[j].size(); k++) {
					dp[i][j] = max(dp[i][j], dp[i + 1][X[j][k]] + 1);
					if (j == X[j][k]) dp[i][j] = INF;
				}
				if (dp[i][j] >= N + 1) dp[i][j] = INF;
			}
		}
	}
	
	/*cout << "--- DP Table ---" << endl;
	for (int i = 0; i <= S + 1; i++) {
		printf("#% 3d: ", i);
		for (int j = 0; j < N; j++) printf("% 2d", dp[i][j]);
		printf("\n");
	}
	printf("\n");*/
	
	vector<int>ans;
	for (int i = 0; i < N; i++) {
		if (dp[0][i] == INF) ans.push_back(0);
		else ans.push_back(1);
	}
	return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	init();
	N = a.size(); M = u.size(); bool s1 = true;
	for (int i = 0; i < N; i++) { A[i] = a[i]; R[i] = r[i]; }
	for (int i = 0; i < M; i++) { U[i] = u[i]; V[i] = v[i]; if (V[i] - U[i] < 0 || V[i] - U[i] >= 2) s1 = false; }
	
	if (s1 == true) return solve_subtask1();
	return solve_subtask2();
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> solve_subtask2()':
train.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < X[j].size(); k++) { if (dp[i + 1][X[j][k]] == INF) cnt++; }
                     ~~^~~~~~~~~~~~~
train.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < X[j].size(); k++) {
                     ~~^~~~~~~~~~~~~
train.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < X[j].size(); k++) {
                     ~~^~~~~~~~~~~~~

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