Submission #859478

#	Time	Username	Problem	Language	Result	Execution time	Memory
859478		maks007	Viruses (BOI20_viruses)	C++14	0 / 100	1 ms	604 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);
	for(auto i : mp[2]) {
		for(auto j : i) {
			assert(j <= 2);
			if(j == 2) goto end;
		}
		dp[2] = min(dp[2], (int)i.size());
		end:;
	}
	for(int i = 3; i < G; i ++) {
		int mn = 1e9;
		for(auto j : mp[i]) {
			int ans = 0;
			for(auto k : j) {
				assert(k <= i);
				if(k == i) goto end2;
				if(k > 1) ans += dp[k];
				else ans ++;
			}
			mn = min(mn, ans);
			end2:;
		}
		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