#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
