Submission #153962

#	Time	Username	Problem	Language	Result	Execution time	Memory
153962		Swan	Political Development (BOI17_politicaldevelopment)	C++14	4 / 100	3017 ms	145392 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
using namespace std;

typedef long long ll;

vector<vector<int>> v;

int ans = 0;
int n,k;

const int maxn = 1e5;
bitset<12> way[12];
int num[maxn];
map<pair<int,int>,bool> is_good;

bool check(int mask,int cnt){
    int res = (1<<22)-1;
    for(int i(0); i < cnt+1;i++){
        if(mask&(1<<i)){
            int to = way[i].to_ullong();
            res&=to;
        }
    }
    for(int i(0); i < cnt+1;i++){
        if(mask&(1<<i)){
            int bit = res&(1<<i);
            if(!bit)return 0;
        }
    }
    /*if(mask == 15){
        for(int i(0); i < 6;i++)cerr << (bool)(res&(1<<i));
        stop;
    }*/
    /*if(mask == 15){
        for(int i(0); i < 4;i++){
            for(int j(0); j < 4;j++){
                cerr << way[i][j] << ' ';
            }
            cerr << endl;
        }
        cerr << endl;
        cerr << mask << ' ' << res << endl;
        stop;
    }*/
    return 1;
}

void solve(int u){
    int pnt = 0;
    vector<int> qwe;
    qwe.push_back(u);
    for(int i(0); i < 12;i++)way[i] = 0;
    for(int i(0); i < v[u].size();i++){
        way[pnt][pnt] = 1;
        num[v[u][i]] = pnt++;
        qwe.push_back(v[u][i]);
    }
    num[u] = pnt;
    way[pnt][pnt] = 1;
    for(int i(0); i < qwe.size();i++){
        for(int j(0); j < qwe.size();j++){
            bool f = (is_good[{qwe[i],qwe[j]}] && is_good[{qwe[j],qwe[i]}]);
            if(!f){
                continue;
            }
            way[num[qwe[i]]][num[qwe[j]]] = 1;
        }
    }
    /*cout << u << endl;
        for(int i(0); i < 4;i++){
            for(int j(0); j < 4;j++){
                cout << way[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl;*/
    int lim = (1<<(v[u].size()+1));
    for(int i(0); i < lim;i++){
        bool f = check(i,v[u].size());
        if(!f)continue;
        int x = i;
        int now = 0;
        while(x){
            now+=(x%2);
            x/=2;
        }
        //if(u == 0)cout << i << ' ' << now << endl;
        ans = max(now,ans);
    }
}

main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    v.resize(n+2);
    for(int i(0); i < n;i++){
        int sz; cin >> sz;
        for(int j(0); j < sz;j++){
            int x; cin >> x;
            v[i].push_back(x);
            is_good[{i,x}] = 1;
        }
    }
    for(int i(0); i < n;i++){
        if(v[i].size() < k)solve(i);
    }
    cout << ans;
    return 0;
}
/*
4 10
3 1 2 3
3 0 3 2
2 1 3
3 0 1 2
*/

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:63:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < qwe.size();i++){
                   ~~^~~~~~~~~~~~
politicaldevelopment.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0); j < qwe.size();j++){
                       ~~^~~~~~~~~~~~
politicaldevelopment.cpp: At global scope:
politicaldevelopment.cpp:95:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size() < k)solve(i);
            ~~~~~~~~~~~~^~~

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