# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
636951 | 2022-08-30T16:30:53 Z | BidoTeima | Bosses (BOI16_bosses) | C++17 | 1 ms | 600 KB |
/// isA AC #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename t1> using ordered_set = tree<t1, null_type,less<t1>, rb_tree_tag,tree_order_statistics_node_update>; using ll = long long; void moo(string filename); void ACPLS(string str = "") { if(str=="NOF")return; if(str.size()) moo(str); else{ #ifndef ONLINE_JUDGE freopen("output.txt", "w", stdout); freopen("input.txt", "r", stdin); #endif } ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } void moo(string fileName){ freopen((fileName+".in").c_str(),"r",stdin); freopen((fileName+".out").c_str(),"w",stdout); } #define tc \ int tttttt,subtask; \ cin >> tttttt /*>> subtask*/; \ while (tttttt--) #define sumrange(l, r, arr) (l == 0 ? arr[r] : arr[r] - arr[l - 1]) #define all(v) v.begin(), v.end() vector<int>canBeChildren[5005]; vector<int>adj[5005]; vector<int>adj_rev[5005]; vector<bool>vis(5005); ll salary[5005]; vector<int>topo; void dfs(int node){ vis[node] = 1; for(int possibleChild : canBeChildren[node]){ if(!vis[possibleChild]){ vis[possibleChild] = 1; adj[node].push_back(possibleChild); adj_rev[possibleChild].push_back(node); dfs(possibleChild); } } topo.push_back(node); } void dfs_rev(int node){ salary[node] += 1; for(int parent : adj_rev[node]){ salary[parent] += salary[node]; } } int main() { ACPLS("NOF"); int n; cin>>n; for(int i = 1; i <= n; i++){ int k; cin>>k; for(int j = 0; j < k; j++){ int parent; cin>>parent; canBeChildren[parent].push_back(i); } } ll ans = 1e18; int root = -1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= 5000; j++){ adj[j].clear(); adj_rev[j].clear(); vis[j] = 0; salary[j] = 0; } topo.clear(); dfs(i); bool ok = 1; for(int j = 1; j <= n; j++){ if(!vis[j]){ ok = 0; break; } } if(!ok)continue; for(int node : topo){ dfs_rev(node); } ll res = 0; for(int j = 1; j <= n; j++){ res+=salary[j]; } if(res<ans){ ans = res; root = i; } } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Incorrect | 1 ms | 600 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Incorrect | 1 ms | 600 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Incorrect | 1 ms | 600 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |