Submission #120051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120051	2019-06-23T06:22:20 Z	E869120	File Paths (BOI15_fil)	C++14	33 / 100	1000 ms	76636 KB

fil

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

int N, M, K, S, dist[6009], dp[6009][6009]; 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 <= 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;
				int pos1 = lower_bound(E2.begin(), E2.end(), cl) - E2.begin();
				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 = lower_bound(E1.begin(), E1.end(), cl) - E1.begin();
				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

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:54: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:59: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:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E1.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:66: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:69: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:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E2.size(); i++) {
                  ~~^~~~~~~~~~~
fil.cpp:76: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:79: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.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6016 KB	Output is correct
2	Correct	18 ms	8056 KB	Output is correct
3	Correct	33 ms	9472 KB	Output is correct
4	Correct	26 ms	8420 KB	Output is correct
5	Correct	32 ms	9444 KB	Output is correct
6	Correct	29 ms	9464 KB	Output is correct
7	Correct	31 ms	9472 KB	Output is correct
8	Correct	29 ms	9600 KB	Output is correct
9	Correct	29 ms	9472 KB	Output is correct
10	Correct	6 ms	5376 KB	Output is correct
11	Correct	21 ms	9216 KB	Output is correct
12	Correct	16 ms	8192 KB	Output is correct

Subtask #2

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1018 ms	76636 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6016 KB	Output is correct
2	Correct	18 ms	8056 KB	Output is correct
3	Correct	33 ms	9472 KB	Output is correct
4	Correct	26 ms	8420 KB	Output is correct
5	Correct	32 ms	9444 KB	Output is correct
6	Correct	29 ms	9464 KB	Output is correct
7	Correct	31 ms	9472 KB	Output is correct
8	Correct	29 ms	9600 KB	Output is correct
9	Correct	29 ms	9472 KB	Output is correct
10	Correct	6 ms	5376 KB	Output is correct
11	Correct	21 ms	9216 KB	Output is correct
12	Correct	16 ms	8192 KB	Output is correct
13	Execution timed out	1018 ms	76636 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-