Submission #120053

#	Time	Username	Problem	Language	Result	Execution time	Memory
120053		E869120	File Paths (BOI15_fil)	C++14	100 / 100	986 ms	85016 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 <= E1.size(); i++) {
		int cl = 0, cr = 1000000;
		if (i >= 1) cl = E1[i - 1] + 1;
		if (i < E1.size()) cr = E1[i];
		for (int j = cl; j <= cr; j++) num1[j] = i;
	}
	for (int i = 0; i <= E2.size(); i++) {
		int cl = 0, cr = 1000000;
		if (i >= 1) cl = E2[i - 1] + 1;
		if (i < E2.size()) cr = E2[i];
		for (int j = cl; j <= cr; j++) num2[j] = i;
	}

	// 全探索
	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;
}

Compilation message (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:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= E1.size(); i++) {
                  ~~^~~~~~~~~~~~
fil.cpp:51:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < E1.size()) cr = E1[i];
       ~~^~~~~~~~~~~
fil.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= E2.size(); i++) {
                  ~~^~~~~~~~~~~~
fil.cpp:57:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < E2.size()) cr = E2[i];
       ~~^~~~~~~~~~~
fil.cpp:67: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:72: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:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E1.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:79: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: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:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E2.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:89: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:92: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: 34 / 34