| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 743183 | hmm789 | Viruses (BOI20_viruses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
vector<vector<int>> adj2[200];
//~ set<int> adj[200];
int ans[200];
bool v[200];
//~ bool cyc(int x) {
//~ if(v[x]) return true;
//~ v[x] = 1;
//~ for(int i : adj[x]) {
//~ bool f = cyc(i);
//~ cout << "a " << x << " " << i << " " << f << endl;
//~ if(f) return true;
//~ }
//~ v[x] = 0;
//~ return false;
//~ }
int dp(int x) {
if(x == 0 || x == 1) return 1;
if(ans[x] == -2) return INF;
if(ans[x] != -1) return ans[x];
if(v[x]) return INF;
v[x] = 1;
ans[x] = INF;
for(vector<int> v : adj2[x]) {
int tmp = 0;
for(int i : v) {
tmp += dp(i);
tmp = min(tmp, INF);
}
//~ cout << " a " << x << " " << v[0] << " " << tmp << endl;
ans[x] = min(ans[x], tmp);
}
//~ cout << " b " << x << " " << ans[x] << endl;
if(ans[x] == INF) ans[x] = -2;
v[x] = 0;
if(ans[x] == -2) return INF;
return ans[x];
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int g, n, m, x, y, a;
cin >> g >> n >> m;
for(int i = 0; i < n; i++) {
cin >> x >> a;
vector<int> tmp;
for(int j = 0; j < a; j++) {
cin >> y;
//~ adj[x].insert(y);
tmp.push_back(y);
}
adj2[x].push_back(tmp);
}
memset(ans, -1, sizeof(ans));
for(int i = 2; i < g; i++) {
if(dp(i) == INF) cout << "YES\n";
else cout << "NO " << dp(i) << '\n';
}
}