Submission #538905

#	Time	Username	Problem	Language	Result	Execution time	Memory
538905		makanhulia	Bosses (BOI16_bosses)	C++17	67 / 100	1577 ms	1028 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, vd[5069], u, v, ans = 1e11, dp[5069], sm;
vector<long long> adj[5069], adj2[5002];
queue<long long> qu;

void dfs(long long cn) {
  dp[cn] = 1;
  for (long long i=0; i<adj2[cn].size(); i++) {
    long long nn = adj2[cn][i];
    dfs(nn);
    dp[cn] += dp[nn];
  }
}

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++) {
    for (long long j=1; j<=n; j++) {
      vd[j] = 0;
    }
    sm = 0;
    qu.push(i);
    vd[i] = 1;
    while (!qu.empty()) {
      u = qu.front();
      qu.pop();
      for (long long j=0; j<adj[u].size(); j++) {
        v = adj[u][j];
        if (vd[v] == 0) {
          vd[v] = 1;
          qu.push(v);
          adj2[u].push_back(v);
        }
      }
    }
    dfs(i);
    for (long long j=1; j<=n; j++) {
      adj2[j].clear();
    }
    if (dp[i]<n) {
      continue;
    }
    for (long long j=1; j<=n; j++) {
      sm += dp[j];
    }
    ans = min(ans, sm);
  }
  cout << ans << "\n";
  otsumiko
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(long long int)':
bosses.cpp:15:24: 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]
   15 |   for (long long i=0; i<adj2[cn].size(); i++) {
      |                       ~^~~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:42: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]
   42 |       for (long long j=0; j<adj[u].size(); j++) {
      |                           ~^~~~~~~~~~~~~~

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