Submission #46795

#	Time	Username	Problem	Language	Result	Execution time	Memory
46795		Lkvatashidze	Bosses (BOI16_bosses)	C++17	100 / 100	1040 ms	888 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
const int INF=200000000;
using namespace std;

        vector < vector < int > > g;
        vector < int > used;
        vector < int > cnt;

 int main() {


     ios::sync_with_stdio(false);
     cin.tie(0);

        int n;
         cin >> n;

     g.resize(n+1); used.resize(n+1); cnt.resize(n+1);

      for (int k=1; k<=n; k++) {

         int ct;
          cin >> ct;
        for (int j=1; j<=ct; j++) {
             int a;
              cin >> a;
              g[a].push_back(k);
        }
    }

         int ans=INF;

      for (int i=1; i<=n; i++) {

         queue < pair < int, int > > Q;
         stack < pair < int, int > > stc;

         Q.push({i,-1}); used[i]=1;

          while (!Q.empty()) {
            pair < int, int > v=Q.front();
             Q.pop();
            stc.push(v);
            for (int k=0; k<g[v.first].size(); k++) {
                 if (!used[g[v.first][k]]) {
                    Q.push({g[v.first][k],v.first});
                    used[g[v.first][k]]=1;
                 }
            }
    }

        bool ind=true;
      for (int i=1; i<=n; i++) {
         if (used[i]==0) { ind=false; break; }
      }

        if (ind) {

            while (!stc.empty()) {
                     pair < int, int > v=stc.top();
                     stc.pop();

                       if (!stc.empty()) {
                        cnt[v.first]++;
                        cnt[v.second]+=cnt[v.first];
                       } else {
                         cnt[v.first]++;
                    }
            }

             int temp=0;

        for (int i=1; i<=n; i++)
            temp+=cnt[i];

         ans=min(ans,temp);
    }


         for (int k=1; k<=n; k++) used[k]=0,cnt[k]=0;
 }

      cout << ans;

    return 0;
 }

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:45:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k=0; k<g[v.first].size(); k++) {
                           ~^~~~~~~~~~~~~~~~~~

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