Submission #53621

#	Time	Username	Problem	Language	Result	Execution time	Memory
53621		ruhanhabib39	Bosses (BOI16_bosses)	C++17	100 / 100	826 ms	1308 KiB

bosses

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

const int MAXN = 5000;

int N;
vector<int> par[MAXN + 10];
vector<int> child[MAXN + 10];
int done[MAXN + 10];
int salary[MAXN + 10];

int vec[MAXN + 10], ii = 0;
int boss[MAXN + 10];

int work(int root) {
   ii = 0;
   queue<int> q; q.push(root);
   done[root] = root; boss[root] = -1;
   while(!q.empty()) {
      int u = q.front(); q.pop();
      vec[ii++] = u;
      for(int v : child[u]) {
         if(done[v] == root) continue;
         done[v] = root;
         boss[v] = u;
         q.push(v);
      }
   }
   for(int u = 1; u <= N; u++) {
      if(done[u] != root) return 1e9;
   }
   fill(salary, salary + N + 1, 1);
   int res = 0;
   for(int i = ii-1; i >= 0; i--) {
      int v = vec[i];
      if(boss[v] != -1) salary[boss[v]] += salary[v];
      res += salary[v];
   }
   return res;
}

int main() {
   scanf("%d", &N);
   for(int u = 1; u <= N; u++) {
      int sz; scanf("%d", &sz);
      par[u].resize(sz);
      for(int& p : par[u]) {
         scanf("%d", &p);
         child[p].push_back(u);
      }
   }
   int res = 1e9;
   for(int u = 1; u <= N; u++) res = min(res, work(u));
   printf("%d\n", res);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &N);
    ~~~~~^~~~~~~~~~
bosses.cpp:45:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int sz; scanf("%d", &sz);
               ~~~~~^~~~~~~~~~~
bosses.cpp:48:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d", &p);
          ~~~~~^~~~~~~~~~

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