oj.uz

Submission #695148

# Submission time Handle Problem Language Result Execution time Memory
695148 2023-02-04T18:45:35 Z edogawa_something Bosses (BOI16_bosses) C++17
100 / 100
 1437 ms 94596 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string st;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define pu push
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(ll i=0;i<n;i++)
#define forx(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pof pop_front
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
const ll dx[]{1,0,-1,0};
const ll dy[]{0,-1,0,1};
const ll inf=2e18;
const ll mod=1e9+7;
const ll LM=2e7+1;
const ll M=2e6+1;
const ll MM=1002;
const ll MMM=501;
const ld pi=acos(-1);
//const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  r%=mod;
  while(to){
    if((to&1)){
      res*=r,res%=mod;
    }
    r*=r,r%=mod;
    to=(to>>1);
  }
  return res;
}
int n,ans;
vector<int> k[M];
bl vis[M];
vector<int> v[M];
int salary[M];
int dfs(int r){
  int res=1;
  for(auto it:v[r])
  res+=dfs(it);
  salary[r]=res;
  return salary[r];
}
ll chk(ll r){
  forx(i,1,n+1)
  vis[i]=0;
  forx(i,1,n+1)
  v[i].clear();
  queue<int>q;
  q.push(r);
  vis[r]=1;
  while(q.size()){
    int x=q.front();
    q.pop();
    for(auto it:k[x]){
      if(vis[it])
      continue;
      v[x].pb(it),q.push(it),vis[it]=1;
    }
  }
  forx(i,1,n+1){
    if(!vis[i])
    return inf;
  }
  ll res=0;
  dfs(r);
  forx(i,1,n+1)
  res+=salary[i];
  return res;
}
int main(){
  fast
  ll ans=inf;
  cin>>n;
  forn(i,n){
    ll x;
    cin>>x;
    while(x--){
      ll y;
      cin>>y;
      k[y].pb(i+1);
    }
  }
  forx(i,1,n+1)
  ans=min(ans,chk(i));
  cout<<ans;
  return 0;
}
/*

*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94208 KB Output is correct
2 Correct 44 ms 94188 KB Output is correct
3 Correct 45 ms 94156 KB Output is correct
4 Correct 50 ms 94248 KB Output is correct
5 Correct 44 ms 94140 KB Output is correct
6 Correct 44 ms 94184 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94208 KB Output is correct
2 Correct 44 ms 94188 KB Output is correct
3 Correct 45 ms 94156 KB Output is correct
4 Correct 50 ms 94248 KB Output is correct
5 Correct 44 ms 94140 KB Output is correct
6 Correct 44 ms 94184 KB Output is correct
7 Correct 44 ms 94244 KB Output is correct
8 Correct 45 ms 94164 KB Output is correct
9 Correct 47 ms 94212 KB Output is correct
10 Correct 45 ms 94188 KB Output is correct
11 Correct 53 ms 94256 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94208 KB Output is correct
2 Correct 44 ms 94188 KB Output is correct
3 Correct 45 ms 94156 KB Output is correct
4 Correct 50 ms 94248 KB Output is correct
5 Correct 44 ms 94140 KB Output is correct
6 Correct 44 ms 94184 KB Output is correct
7 Correct 44 ms 94244 KB Output is correct
8 Correct 45 ms 94164 KB Output is correct
9 Correct 47 ms 94212 KB Output is correct
10 Correct 45 ms 94188 KB Output is correct
11 Correct 53 ms 94256 KB Output is correct
12 Correct 56 ms 94404 KB Output is correct
13 Correct 51 ms 94300 KB Output is correct
14 Correct 271 ms 94512 KB Output is correct
15 Correct 84 ms 94428 KB Output is correct
16 Correct 737 ms 94532 KB Output is correct
17 Correct 1437 ms 94596 KB Output is correct
18 Correct 1411 ms 94596 KB Output is correct