답안 #120053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120053	2019-06-23T06:27:55 Z	E869120	File Paths (BOI15_fil)	C++14	100 / 100	986 ms	85016 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], 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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