Submission #139766

#	Time	Username	Problem	Language	Result	Execution time	Memory
139766		rzbt	Bosses (BOI16_bosses)	C++14	67 / 100	1571 ms	1016 KiB

bosses

    #include <bits/stdc++.h>
    #define MAXN 5005
    #define pb push_back
    using namespace std;
     
    int n;
    vector<int> niz[MAXN];
    vector<int> cudni[MAXN];
     
    queue<int> q;
    int posecen[MAXN];
    int tp;
    void bfs(int s){
        int t;
     
        for(int i=1;i<=n;i++)
            if(!cudni[i].empty())
                cudni[i].clear();
        tp=0;
        q.push(s);
        posecen[s]=s;
        while(!q.empty()){
            tp++;
            t=q.front();
            q.pop();
            for(auto x:niz[t]){
                if(posecen[x]==s)continue;
                cudni[t].pb(x);
                posecen[x]=s;
                q.push(x);
            }
        }
     
    }
     
    int res=1e9;
    int ucena;
    int dfs(int t){
     
        int cena=1;
        for(auto x:cudni[t])
            cena+=dfs(x);
     
        ucena+=cena;
        return cena;
     
    }
     
    int main()
    {
        scanf("%d", &n);
        for(int i=1;i<=n;i++){
            int tk;
            scanf("%d", &tk);
            for(int j=0;j<tk;j++){
                int t;
                scanf("%d", &t);
                niz[t].pb(i);
            }
        }
        for(int i=1;i<=n;i++){
            bfs(i);
     
            if(tp!=n)continue;
     
            ucena=0;
            dfs(i);
            res=min(res,ucena);
        }
        printf("%d",res);
        return 0;
    }//

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
         ~~~~~^~~~~~~~~~
bosses.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &tk);
             ~~~~~^~~~~~~~~~~
bosses.cpp:57:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &t);
                 ~~~~~^~~~~~~~~~

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