oj.uz

Submission #743102

# Submission time Handle Problem Language Result Execution time Memory
743102 2023-05-17T08:04:11 Z beepbeepsheep Viruses (BOI20_viruses) C++17
0 / 100
 1 ms 596 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 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 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -