Submission #540879

#	Time	Username	Problem	Language	Result	Execution time	Memory
540879		skittles1412	Viruses (BOI20_viruses)	C++17	11 / 100	1 ms	468 KiB

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 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18