제출 #113495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113495		E869120	장난감 기차 (IOI17_train)	C++14	49 / 100	1480 ms	217324 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) 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) 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;
}

bool used[5009][5009];

void dfs(int fir, int pos) {
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[fir][X[pos][i]] == true) continue;
		used[fir][X[pos][i]] = true;
		dfs(fir, X[pos][i]);
	}
}

vector<int> solve_subtask3() {
	for (int i = 0; i < M; i++) X[U[i]].push_back(V[i]);
	for (int i = 0; i < N; i++) dfs(i, i);
	
	vector<int>ans;
	for (int i = 0; i < N; i++) {
		bool ok = false;
		for (int j = 0; j < N; j++) {
			if (used[i][j] == true && used[j][j] == true && R[j] == 1) ok = true;
		}
		ans.push_back((int)ok);
	}
	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; bool s3 = true;
	for (int i = 0; i < N; i++) { A[i] = a[i]; R[i] = r[i]; if (A[i] == 0) s3 = false; }
	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 (s3 == true) return solve_subtask3();
	if (s1 == true) return solve_subtask1();
	return solve_subtask2();
}

컴파일 시 표준 에러 (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++) {
                     ~~^~~~~~~~~~~~~
train.cpp: In function 'void dfs(int, int)':
train.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~

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