Submission #743102

#	Time	Username	Problem	Language	Result	Execution time	Memory
743102		beepbeepsheep	Viruses (BOI20_viruses)	C++17	0 / 100	1 ms	596 KiB

Viruses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll lst[105][105];
ll dp[105];
vector<ll> adj[105];
bool vis[105];
ll solve(ll x){
	cerr<<x<<' '<<dp[x]<<endl;
	if (dp[x]) return dp[x];
	if (vis[x]) return dp[x]=-1;
	ll ans=-1;
	vis[x]=1;
	for (auto u:adj[x]){
		ll curr=0;
		bool cannot=false;
		for (int i=0;i<101;i++){
			if (!lst[u][i]) continue;
			ll res=solve(i);
			if (res==-1){
				cannot=true;
				break;
			}
			curr+=lst[u][i]*res;
		}
		if (cannot) continue;
		if (ans==-1) ans=curr;
		else ans=min(ans,curr);
	}
	vis[x]=0;
	return dp[x]=ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,m,k,b,ele,cnt;
	cin>>n>>m>>k;
	for (int i=1;i<=m;i++){
		cin>>b>>cnt;
		adj[b].emplace_back(i);
		for (int j=1;j<=cnt;j++){
			cin>>ele;
			lst[i][ele]++;
		}
	}
	assert(k==0);
	dp[0]=1;
	dp[1]=1;
	for (int i=2;i<n;i++){
		solve(i);
		if (dp[i]==-1) cout<<"YES"<<endl;
		else cout<<"NO"<<' '<<dp[i]<<endl;
	}
	return 0;
}

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