Submission #113482

#	Time	Username	Problem	Language	Result	Execution time	Memory
113482		E869120	Toy Train (IOI17_train)	C++14	11 / 100	1873 ms	197896 KiB

train

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

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[10009][5009]; vector<int> X[5009];

vector<int> solve_subtask2() {
	for (int i = 0; i < M; i++) X[U[i]].push_back(V[i]);
	
	int S = N + 1;
	for (int i = 2 * S; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			if (R[j] == 1 && i >= S + 1) dp[i][j] = 1; // Borzou の負け
			else if (R[j] == 0 && i == 2 * S) dp[i][j] = 0; // Borzou の勝ち
			else {
				if (A[j] == 1) {
					dp[i][j] = 0;
					for (int k = 0; k < X[j].size(); k++) {
						if (dp[i + 1][X[j][k]] == 1) dp[i][j] = 1;
					}
				}
				else {
					dp[i][j] = 1;
					for (int k = 0; k < X[j].size(); k++) {
						if (dp[i + 1][X[j][k]] == 0) dp[i][j] = 0;
					}
				}
			}
		}
	}
	
	vector<int>ans;
	for (int i = 0; i < N; i++) ans.push_back(dp[0][i]);
	return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	N = a.size(); M = u.size();
	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]; }
	
	return solve_subtask2();
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> solve_subtask2()':
train.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < X[j].size(); k++) {
                      ~~^~~~~~~~~~~~~
train.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < X[j].size(); k++) {
                      ~~^~~~~~~~~~~~~

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