Submission #183939

#	Time	Username	Problem	Language	Result	Execution time	Memory
183939		Ruxandra985	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	538 ms	55280 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define DIMN 50010
using namespace std;
map <int,int> mp[DIMN];
vector <int> v[DIMN];
int grad[DIMN] , f[DIMN] , l[DIMN];
pair <int,int> dp[DIMN];
priority_queue <pair <int,int> > h;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , k , i, elem , nod , vecin , x , ok , ok2 , i2 , j , sol , val , conf;
    fscanf (fin,"%d%d",&n,&k);
    for (i=0;i<n;i++){
        fscanf (fin,"%d",&elem);
        for (j=1;j<=elem;j++){
            fscanf (fin,"%d",&x);
            mp[i][x] = 1;
            v[i].push_back(x);
        }
        grad[i] = elem;
        h.push(make_pair(-grad[i] , i));
    }
    sol = 1;
    while (!h.empty()){
        nod = h.top().second;
        val = -h.top().first;
        h.pop();
        if (grad[nod] != val)
            continue;
        f[nod] = 1;
        /// ok acum avem nodul cu cel mai mic grad
        /// vrei sa vezi daca poate apartine unui graf complet
        elem = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if (!f[vecin]) /// nu are rost sa faci heapul mai mare decat e nevoie
                l[++elem] = vecin;
        }
 
        /// din graful complet curent face parte nod si un subset din l
        ok = 0;
        dp[++ok] = make_pair(0 , 1); /// doar nod
 
        for (i = 1 ; i <= elem ; i++){
 
            ok2 = ok;
            for (j = 1 ; j <= ok2 ; j ++){
                /// adaugi l[i] la configuratia dp[j].first
                x = l[i];
                conf = dp[j].first;
                for (i2 = 0 ; i2 <= k ; i2++){
                    if ( (conf & (1 << i2)) && !mp[x][l[i2+1]] )
                        break;
                }
                if (i2 > k){
                    dp[++ok] = make_pair(conf + (1 << (i-1)) , dp[j].second + 1);
                    sol = max(sol , dp[j].second + 1);
                }
            }
 
        }
 
        /// il eliminam
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            grad[vecin]--;
            if (!f[vecin]) /// nu are rost sa faci heapul mai mare decat e nevoie
                h.push(make_pair(-grad[vecin] , vecin));
        }
    }
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:14:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:16:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&elem);
         ~~~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:18:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&x);
             ~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23