# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
400926 | 2021-05-08T20:46:20 Z | Pichon5 | Bosses (BOI16_bosses) | C++17 | 980 ms | 772 KB |
#include <bits/stdc++.h> #define pb push_back #define vi vector<int> #define F first #define ll long long #define S second #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; vector<vi>G,G2; ll suma[5001]; ll sum=0; vector<bool>vis; void dfs(int nodo, int p){ suma[nodo]=1; for(int i=0;i<G2[nodo].size();i++){ int to=G2[nodo][i]; if(to==p)continue; dfs(to,nodo); suma[nodo]+=suma[to]; } sum+=suma[nodo]; } int main() { fast int n,x,k; cin>>n; G.resize(n+1); for(int i=1;i<=n;i++){ cin>>k; for(int l=0;l<k;l++){ cin>>x; G[x].pb(i); } } ll res=1e16; for(int i=1;i<=n;i++){ G2.assign(n+1,vi()); vis.assign(n+1,false); queue<int>q; int cant=0; q.push(i); vis[i]=1; int dp[n+1]; for(int i=1;i<=n;i++)dp[i]=1; sum=0; while(!q.empty()){ int nodo=q.front(); q.pop(); sum+=dp[nodo]; cant++; for(int l=0;l<G[nodo].size();l++){ int to=G[nodo][l]; if(!vis[to]){ dp[to]+=dp[nodo]; //G2[nodo].pb(to); //G2[to].pb(nodo); vis[to]=1; q.push(to); } } } if(cant!=n){ continue; } //sum=0; //dfs(i,-1); res=min(res,sum); sum=0; } cout<<res<<"\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 2 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 2 ms | 204 KB | Output is correct |
12 | Correct | 8 ms | 332 KB | Output is correct |
13 | Correct | 8 ms | 332 KB | Output is correct |
14 | Correct | 294 ms | 636 KB | Output is correct |
15 | Correct | 145 ms | 588 KB | Output is correct |
16 | Correct | 826 ms | 716 KB | Output is correct |
17 | Correct | 965 ms | 716 KB | Output is correct |
18 | Correct | 980 ms | 772 KB | Output is correct |