oj.uz

Submission #120053

# Submission time Handle Problem Language Result Execution time Memory
120053 2019-06-23T06:27:55 Z E869120 File Paths (BOI15_fil) C++14
100 / 100
 986 ms 85016 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13824 KB Output is correct
2 Correct 21 ms 15872 KB Output is correct
3 Correct 31 ms 17288 KB Output is correct
4 Correct 28 ms 16300 KB Output is correct
5 Correct 51 ms 17272 KB Output is correct
6 Correct 34 ms 17280 KB Output is correct
7 Correct 35 ms 17280 KB Output is correct
8 Correct 38 ms 17280 KB Output is correct
9 Correct 30 ms 17272 KB Output is correct
10 Correct 13 ms 13184 KB Output is correct
11 Correct 26 ms 17024 KB Output is correct
12 Correct 21 ms 16000 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 84572 KB Output is correct
2 Correct 665 ms 84620 KB Output is correct
3 Correct 664 ms 84600 KB Output is correct
4 Correct 668 ms 84600 KB Output is correct
5 Correct 798 ms 84856 KB Output is correct
6 Correct 957 ms 84820 KB Output is correct
7 Correct 832 ms 84856 KB Output is correct
8 Correct 890 ms 84700 KB Output is correct
9 Correct 720 ms 84512 KB Output is correct
10 Correct 694 ms 84600 KB Output is correct
11 Correct 579 ms 79480 KB Output is correct
12 Correct 434 ms 76408 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13824 KB Output is correct
2 Correct 21 ms 15872 KB Output is correct
3 Correct 31 ms 17288 KB Output is correct
4 Correct 28 ms 16300 KB Output is correct
5 Correct 51 ms 17272 KB Output is correct
6 Correct 34 ms 17280 KB Output is correct
7 Correct 35 ms 17280 KB Output is correct
8 Correct 38 ms 17280 KB Output is correct
9 Correct 30 ms 17272 KB Output is correct
10 Correct 13 ms 13184 KB Output is correct
11 Correct 26 ms 17024 KB Output is correct
12 Correct 21 ms 16000 KB Output is correct
13 Correct 707 ms 84572 KB Output is correct
14 Correct 665 ms 84620 KB Output is correct
15 Correct 664 ms 84600 KB Output is correct
16 Correct 668 ms 84600 KB Output is correct
17 Correct 798 ms 84856 KB Output is correct
18 Correct 957 ms 84820 KB Output is correct
19 Correct 832 ms 84856 KB Output is correct
20 Correct 890 ms 84700 KB Output is correct
21 Correct 720 ms 84512 KB Output is correct
22 Correct 694 ms 84600 KB Output is correct
23 Correct 579 ms 79480 KB Output is correct
24 Correct 434 ms 76408 KB Output is correct
25 Correct 650 ms 84428 KB Output is correct
26 Correct 660 ms 84600 KB Output is correct
27 Correct 660 ms 84496 KB Output is correct
28 Correct 672 ms 84564 KB Output is correct
29 Correct 870 ms 84728 KB Output is correct
30 Correct 850 ms 84728 KB Output is correct
31 Correct 986 ms 85016 KB Output is correct
32 Correct 969 ms 84924 KB Output is correct
33 Correct 650 ms 84344 KB Output is correct
34 Correct 631 ms 84568 KB Output is correct
35 Correct 588 ms 84728 KB Output is correct
36 Correct 537 ms 84424 KB Output is correct