Submission #540879

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
540879	2022-03-21T22:37:18 Z	skittles1412	Viruses (BOI20_viruses)	C++17	11 / 100	1 ms	468 KB

Viruses

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const long INF = 1e18;

void solve() {
	int g, n, m;
	cin >> g >> n >> m;
	assert(!m);
	int len[n] {}, type[n];
	int graph[n][g] {};
	for (int i = 0; i < n; i++) {
		int k;
		cin >> type[i] >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			if (x < 2) {
				len[i]++;
			} else {
				graph[i][x]++;
			}
		}
	}
	long dist[g];
	memset(dist, 0x3f, sizeof(dist));
	while (true) {
		bool b = false;
		for (int i = 0; i < n; i++) {
			long cur = len[i];
			for (int j = 0; j < g; j++) {
				if (!graph[i][j]) {
					continue;
				}
				if (dist[j] >= INF) {
					cur = INF;
				} else {
					cur += graph[i][j] * dist[j];
				}
			}
			dbg(i, cur);
			if (cur < dist[type[i]]) {
				dist[type[i]] = cur;
				b = true;
			}
		}
		if (!b) {
			break;
		}
	}
	for (int i = 2; i < g; i++) {
		if (dist[i] >= INF) {
			cout << "YES" << endl;
		} else {
			cout << "NO " << dist[i] << endl;
		}
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	316 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct
19	Correct	1 ms	324 KB	Output is correct
20	Correct	1 ms	316 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	468 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	316 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct
19	Correct	1 ms	324 KB	Output is correct
20	Correct	1 ms	316 KB	Output is correct
21	Runtime error	1 ms	468 KB	Execution killed with signal 6
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	316 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct
19	Correct	1 ms	324 KB	Output is correct
20	Correct	1 ms	316 KB	Output is correct
21	Runtime error	1 ms	468 KB	Execution killed with signal 6
22	Halted	0 ms	0 KB	-