Submission #129907

#	Time	Username	Problem	Language	Result	Execution time	Memory
129907		Abelyan	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	749 ms	82144 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=1e5+10;
const ll MOD=1e9+7;
 
int n,deg[N],vrj[N],ppc[N];
vector<int> g[N];
map<int,bool> mp[N];
priority_queue<pir> pq;
int kp[N],ans=1;
bool pat[N];
void solve(int k){
    vector<int> v;
    trav(to,g[k]){
        if (deg[to])v.ad(to);
    }
    FOR(i,v.size()){
        FOR(j,v.size()){
            if (mp[v[i]][v[j]])kp[i]+=(1<<j);
        }
    }
    //cout<<1<<endl;
    //cout<<k<<endl;
    pat[0]=true;
    FORT(msk,1,(1<<v.size())-1){
        int tv=msk-(1<<vrj[msk]);
        //cout<<msk<<" "<<tv<<" "<<vrj[msk]<<" "<<kp[vrj[msk]]<<" "<<pat[tv]<<" "<<(kp[vrj[msk]]&tv)<<endl;
        if (pat[tv] && ((kp[vrj[msk]]&tv)==tv)){
            //cout<<"yoohoo"<<endl;
            pat[msk]=true;
            ans=max(ans,ppc[msk]+1);
        }
        else{
            pat[msk]=false;
        }
    }
    FOR(i,v.size()){
        kp[i]=0;
        deg[v[i]]--;
        pq.push({-deg[v[i]],v[i]});
    }
    deg[k]=0;
}
 
int main(){
    fastio;
    srng;
    FOR(msk,(1<<10)){
        FOR(i,10){
            if (msk&(1<<i)){
                vrj[msk]=i;
                ppc[msk]++;
            }
        }
    }
    int k;
    cin>>n>>k;
    FOR(i,n){
        int d;
        cin>>d;
        deg[i]=d;
        pq.push({-d,i});
        FOR(j,d){
            int to;
            cin>>to;
            g[i].ad(to);
            mp[i][to]=true;
        }
    }
    while(!pq.empty()){
        int v,dg;
        do{
            v=pq.top().sc;
            //cout<<v<<endl;
            dg=-pq.top().fr;
            pq.pop();
        }while(!pq.empty() && deg[v]!=dg);
        if (pq.empty())break;
        //cout<<1<<endl;
        solve(v);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
politicaldevelopment.cpp:39:5: note: in expansion of macro 'FOR'
     FOR(i,v.size()){
     ^~~
politicaldevelopment.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
politicaldevelopment.cpp:40:9: note: in expansion of macro 'FOR'
         FOR(j,v.size()){
         ^~~
politicaldevelopment.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
politicaldevelopment.cpp:59:5: note: in expansion of macro 'FOR'
     FOR(i,v.size()){
     ^~~

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