Submission #53620

#	Time	Username	Problem	Language	Result	Execution time	Memory
53620		ruhanhabib39	Bosses (BOI16_bosses)	C++17	67 / 100	1567 ms	1680 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];
vector<int> nxt[MAXN + 10];
int salary[MAXN + 10];

int calc(int u) {
   int ss = 0;
   for(int v : nxt[u]) ss += calc(v);
   salary[u] = 1;
   for(int v : nxt[u]) salary[u] += salary[v];
   return ss + salary[u];
}

int work(int root) {
   queue<int> q; q.push(root);
   fill(nxt, nxt + N + 1, vector<int>());
   done[root] = root;
   while(!q.empty()) {
      int u = q.front(); q.pop();
      for(int v : child[u]) {
         if(done[v] == root) continue;
         done[v] = root;
         nxt[u].push_back(v);
         q.push(v);
      }
   }
   for(int u = 1; u <= N; u++) {
      if(done[u] != root) return 1e9;
   }
   return calc(root);
}

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:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &N);
    ~~~~~^~~~~~~~~~
bosses.cpp:43: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:46: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: 0 / 33