Submission #538920

#	Time	Username	Problem	Language	Result	Execution time	Memory
538920		makanhulia	Bosses (BOI16_bosses)	C++17	100 / 100	776 ms	716 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, k, x, u, v, ans = 1e10, sm;
vector<long long> adj[5069];
queue<long long> qu;

int main() {
  nyahalo
  cin >> n;
  for (long long i=1; i<=n; i++) {
    cin >> k;
    for (long long j=1; j<=k; j++) {
      cin >> x;
      adj[x].push_back(i);
    }
  }
  for (long long i=1; i<=n; i++) {
    long long dp[n+1], ps[n+1] = {0};
    memset(dp, -1, sizeof(dp));
    sm = 0;
    qu.push(i);
    dp[i] = 0;
    ps[0]++;
    while (!qu.empty()) {
      u = qu.front();
      qu.pop();
      for (long long j=0; j<adj[u].size(); j++) {
        v = adj[u][j];
        if (dp[v] == -1) {
          dp[v] = dp[u]+1;
          ps[dp[v]]++;
          qu.push(v);
        }
      }
    }
    for (long long i=0; i<n; i++) {
      if (i>0) {
        ps[i] += ps[i-1];
      }
      sm += n-ps[i];
    }
    sm += n;
    if (ps[n-1]<n) {
      continue;
    }
    ans = min(ans, sm);
  }
  cout << ans << "\n";
  otsumiko
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:33:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |       for (long long j=0; j<adj[u].size(); j++) {
      |                           ~^~~~~~~~~~~~~~

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