Submission #531068

#	Time	Username	Problem	Language	Result	Execution time	Memory
531068		Majed	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	332 KiB

bosses

#include <bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define quick ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);
typedef long long ll;

using namespace std;

const int N = 5001;

bool vis[N] = {false};

// bool prime[N+1];

vector<int>adj[N];
vector<int>v;
map<int,int>mp;

void bfs(int s) {
  v.clear();
  memset(vis,false,sizeof(vis));
  queue<int>q;
  vis[s] = true;
  q.push(s);
  v.push_back(s);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (int child : adj[node]) {
      if (!vis[child]) {
        vis[child] = true;
        q.push(child);
        v.push_back(child);
      }
    }
  }
}

int main() {
    quick;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      int k;
      cin >> k;
      for (int j = 0; j < k; j++) {
        int u;
        cin >> u;
        adj[u].push_back(i);
        // adj[i].push_back(u);
      }
    }
    ll mn = LLONG_MAX;
    ll sum;
    for (int i = 1; i <= n; i++) {
      int c = 0;
      sum = 0;
      bfs(i);
      mp.clear();
      if (v.size() != n)
        continue;
      reverse(all(v));
      memset(vis,false,sizeof(vis));
      for (int i = 0; i < v.size(); i++) {
        vis[v[i]] = true;
        for (int child : adj[v[i]]) {
          if (vis[child]) {
            mp[v[i]] += mp[child];
          }
        }
        mp[v[i]]++;
        sum += mp[v[i]];
      }
      mn = min(sum,mn);
    }
    cout << mn << endl;

    // while (!root.empty()) {
    //   queue<int>q;
    //   int level[N];
    //   memset(level,0,sizeof(level));
    //
    //
    //   int u = root.front();
    //   q.push(u);
    //   level[u] = 1;
    //   vis[u] = true;
    //
    //   while (!q.empty()) {
    //     int node = q.front();
    //     q.pop();
    //     for (int child : adj[node]) {
    //       if (!vis[child]) {
    //         vis[child] = true;
    //         q.push(child);
    //         level[child] = level[node] + 1;
    //         mx = max(mx, level[child]);
    //       }
    //     }
    //   }
    //   root.pop();
    // }
    // cout << mx << endl;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |       if (v.size() != n)
      |           ~~~~~~~~~^~~~
bosses.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |       for (int i = 0; i < v.size(); i++) {
      |                       ~~^~~~~~~~~~
bosses.cpp:56:11: warning: unused variable 'c' [-Wunused-variable]
   56 |       int c = 0;
      |           ^

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