Submission #533492

#	Time	Username	Problem	Language	Result	Execution time	Memory
533492		kebine	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	460 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll N,M,memo[5005];
bool visited[5005];
vector <ll> adj[5005];
ll dp(ll x){
  if(memo[x]!=-1){
    return memo[x];
  }
  vector <ll> vec;
  for(int i=0;i<adj[x].size();i++){
    if(!visited[adj[x][i]]){
      vec.push_back(adj[x][i]);
      visited[adj[x][i]]=true;
    }
  }
  ll ret=1;
  for(int i=0;i<vec.size();i++){
    ret+=dp(vec[i]);
  }
  return memo[x]=ret;
}
int main(){
  cin>>N;
  for(int i=1;i<=N;i++){
    cin>>M;
    for(int j=1;j<=M;j++){
      ll temp;
      cin>>temp;
      adj[temp].push_back(i);
    }
  }
  ll minn=1e18;
  for(int i=1;i<=N;i++){
    memset(visited,false,sizeof(visited));
    memset(memo,-1,sizeof(memo));
    visited[i]=true;
    ll temp=dp(i);
    ll sum=0;
    bool ok=true;
    for(int j=1;j<=N;j++){
      sum+=memo[j];
      if(memo[j]==-1){
        ok=false;
        break;
      }
    }
    if(!ok){
      continue;
    }
    minn=min(minn,sum);
  }
  cout<<minn<<endl;
}

Compilation message (stderr)

bosses.cpp: In function 'long long int dp(long long int)':
bosses.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int i=0;i<adj[x].size();i++){
      |               ~^~~~~~~~~~~~~~
bosses.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0;i<vec.size();i++){
      |               ~^~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:42:8: warning: unused variable 'temp' [-Wunused-variable]
   42 |     ll temp=dp(i);
      |        ^~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33