Submission #859479

#	Time	Username	Problem	Language	Result	Execution time	Memory
859479		maks007	Viruses (BOI20_viruses)	C++14	0 / 100	174 ms	262144 KiB

Viruses

#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long
 
// vector <vector <pair <int,int>>> g;
// vector <int> used;
// vector <int> comp;

// #define int long long

// void dfs(int v) {
// 	used[v] = 1;
// 	for(auto [i, j] : g[v]) {
// 		if(used[i] == LLONG_MAX) dfs(i);
// 	}
// }

// void get_comps() {
// 	for(int i = 0; i < used.size(); i ++) {
// 		if(used[i] == LLONG_MAX) {
// 			dfs(i);
// 			comp.push_back(i);
// 		}
// 	}
// }

// int check(int v) {
// 	int f = 1;
// 	for(auto [i, j] : g[v]) {
// 		if(used[i] == LLONG_MAX) {
// 			used[i] = j - used[v];
// 			f = min(f, check(i));
// 		}else {
// 			if(used[i] + used[v] != j) f = 0;
// 		}
// 	}
// 	return f;
// }

// vector <pair <int,int>> rec(int v) {
// 	int mn = LLONG_MAX;
// 	vector <pair <int,int>> ans;
// 	for(int val = -100; val <= 100; val += 1) {
// 		for(auto &j : used) j = LLONG_MAX;
// 		used[v] = val;
// 		if(check(v)) {
// 			int cnt = 0;
// 			for(auto &j : used) {
// 				if(j == LLONG_MAX) continue;
// 				cnt += abs(j);
// 			}
// 			if(cnt <= mn) {
// 				mn = cnt;
// 				for(int j = 0; j < used.size(); j ++) {
// 					if(used[j] == LLONG_MAX) continue;
// 					ans.push_back({j, used[j]});
// 				}
// 			}
// 		}
// 		// cout << val << " ";
// 		// if(val == 0.5) {
// 		// 	for(auto j : used) cout << j << " ";
// 		// }
// 	}
// 	if(mn == LLONG_MAX) {
// 		cout << "NO\n";
// 		exit(0);
// 	}
// 	return ans;
// }

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int G, N, M;
	cin >> G >> N >> M;
	assert(M == 0);
	map <int, vector <vector <int>>> mp;
	for(int i = 0; i < N; i ++) {
		int x;
		cin >> x;
		int sz;
		cin >> sz;
		vector <int> temp;
		for(int j = 0; j < sz; j ++) {
			int var;
			cin >> var;
			temp.push_back(var);
		}
		mp[x].push_back(temp);
	}
	vector <int> dp(G, 1e9);
	function <int(vector <int>, int)> get=[&](vector <int> v, int n) {
		int cnt = 0;
		for(auto i : v) {
			if(i == n) return (int)1e9;
			if(i == 1 || i == 0) {
				cnt ++;
			}else 
			if(dp[i] != (int)1e9) cnt += dp[i];
			else {
				int mn = (int)1e9;
				for(auto j : mp[i]) {
					mn = min(mn, get(j, i));
				}
				cnt += mn;
			}
		}
		return cnt;
	};
	for(int i = 2; i < G; i ++) {
		int mn = 1e9;
		for(auto j : mp[i]) {
			mn = min(mn, get(j, i));
		}
		dp[i] = mn;
	}
	for(int i = 2; i < G; i ++) {
		cout << "NO " << dp[i] << "\n";
	}
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18