제출 #120052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120052		E869120	File Paths (BOI15_fil)	C++14	66 / 100	1012 ms	84988 KiB

fil

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, M, K, S, dist[6009], dp[6009][6009], num1[1000009], num2[1000009]; bool used[6009], flag[6009];
vector<pair<int, int>>G[6009], I[6009];
vector<int>E1, E2, F1[100009], F2[100009];

void dfs1(int pos, int dep) {
	dist[pos] = dep;
	for (int i = 0; i < G[pos].size(); i++) dfs1(G[pos][i].first, dep + G[pos][i].second);
}

void dfs2(int root, int pos, int dep) {
	if (dp[root][pos] != (1 << 30)) return;
	dp[root][pos] = dep;
	for (int i = 0; i < I[pos].size(); i++) dfs2(root, I[pos][i].first, dep + I[pos][i].second);
}

int main() {
	scanf("%d%d%d%d", &N, &M, &K, &S); S++;
	for (int i = 1; i <= N + M; i++) {
		int p, l; scanf("%d%d", &p, &l); l++;
		G[p].push_back(make_pair(i, l));
		I[p].push_back(make_pair(i, l));
		I[i].push_back(make_pair(p, l));
	}

	// 前準備
	dfs1(0, 0);
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N + M; j++) dp[i][j] = (1 << 30);
		dfs2(i, i, 0);
	}
	for (int i = N + 1; i <= N + M; i++) {
		E1.push_back(dist[i]);
		for (int j = 1; j * j <= (K - dist[i]); j++) {
			if ((K - dist[i]) % j != 0) continue;
			E2.push_back(j);
			E2.push_back((K - dist[i]) / j);
		}
	}
	sort(E1.begin(), E1.end()); E1.erase(unique(E1.begin(), E1.end()), E1.end());
	sort(E2.begin(), E2.end()); E2.erase(unique(E2.begin(), E2.end()), E2.end());

	for (int i = 0; i <= 1000000; i++) num1[i] = lower_bound(E1.begin(), E1.end(), i) - E1.begin();
	for (int i = 0; i <= 1000000; i++) num2[i] = lower_bound(E2.begin(), E2.end(), i) - E2.begin();

	// 全探索
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			if (dist[i] >= dist[j] && dist[j] + dp[j][i] == dist[i]) {
				int cl = dp[j][i] + S; if (cl < 0 || cl > K) continue;
				int pos1 = num2[cl];
				if (pos1 < E2.size() && E2[pos1] == cl) F2[pos1].push_back(j);
			}
			else {
				int cl = dist[i] + S - dist[j]; cl = K - cl;
				int pos1 = num1[cl]; if (cl < 0 || cl > K) continue;
				if (pos1 < E1.size() && E1[pos1] == cl) F1[pos1].push_back(j);
			}
		}
	}

	for (int i = 0; i < E1.size(); i++) {
		for (int j = 0; j <= N + M; j++) used[j] = false;
		for (int j = 0; j < F1[i].size(); j++) used[F1[i][j]] = true;
		for (int j = 0; j <= N; j++) {
			if (used[j] == false) continue;
			for (int k = 0; k < G[j].size(); k++) used[G[j][k].first] = true;
		}
		for (int j = N + 1; j <= N + M; j++) { if (used[j] == true && dist[j] == E1[i]) flag[j] = true; }
	}

	for (int i = 0; i < E2.size(); i++) {
		for (int j = 0; j <= N + M; j++) used[j] = false;
		for (int j = 0; j < F2[i].size(); j++) used[F2[i][j]] = true;
		for (int j = 0; j <= N; j++) {
			if (used[j] == false) continue;
			for (int k = 0; k < G[j].size(); k++) used[G[j][k].first] = true;
		}
		for (int j = N + 1; j <= N + M; j++) { if (used[j] == true && (K - dist[j]) % E2[i] == 0) flag[j] = true; }
	}

	for (int i = N + 1; i <= N + M; i++) {
		if (flag[i] == true) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fil.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
fil.cpp: In function 'void dfs1(int, int)':
fil.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) dfs1(G[pos][i].first, dep + G[pos][i].second);
                  ~~^~~~~~~~~~~~~~~
fil.cpp: In function 'void dfs2(int, int, int)':
fil.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I[pos].size(); i++) dfs2(root, I[pos][i].first, dep + I[pos][i].second);
                  ~~^~~~~~~~~~~~~~~
fil.cpp: In function 'int main()':
fil.cpp:57:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos1 < E2.size() && E2[pos1] == cl) F2[pos1].push_back(j);
         ~~~~~^~~~~~~~~~~
fil.cpp:62:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos1 < E1.size() && E1[pos1] == cl) F1[pos1].push_back(j);
         ~~~~~^~~~~~~~~~~
fil.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E1.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < F1[i].size(); j++) used[F1[i][j]] = true;
                   ~~^~~~~~~~~~~~~~
fil.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < G[j].size(); k++) used[G[j][k].first] = true;
                    ~~^~~~~~~~~~~~~
fil.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E2.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < F2[i].size(); j++) used[F2[i][j]] = true;
                   ~~^~~~~~~~~~~~~~
fil.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < G[j].size(); k++) used[G[j][k].first] = true;
                    ~~^~~~~~~~~~~~~
fil.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &M, &K, &S); S++;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p, l; scanf("%d%d", &p, &l); l++;
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 0 / 34