Submission #1115890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115890		flyingkite	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	723 ms	333052 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 1e3;
bitset<50005>b[50005], cur;
ll n,k;    
void to_thic_cau(){
    cin >> n >> k;
    vector<vector<ll>>prv;
    for(ll i = 0; i < n;i++){
        prv.pb({i});   
        ll sz; cin >> sz;
        while(sz--){
            ll v; cin >> v;
            b[min(i, v)][max(i, v)] = 1;
        }
    }
    for(int i = 2; i <= k + 1;i++){
        vector<vector<ll>>nxt;
        for(auto vec : prv){
            cur = b[vec[0]];
            for(int j = 1; j < vec.size();j++) cur &= b[vec[j]];
            for(int j = cur._Find_first(); j < n; j = cur._Find_next(j)){
                vector<ll>tmp = vec;
                tmp.pb(j);
                nxt.pb(tmp);
            }
        }
        prv.clear(); prv = nxt;
        if(!prv.size()){
            cout << i - 1 << "\n";
            return;
        } 
    }
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1;   
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message (stderr)

politicaldevelopment.cpp:12:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const ll inf = 1e18;
      |                ^~~~
politicaldevelopment.cpp: In function 'void to_thic_cau()':
politicaldevelopment.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int j = 1; j < vec.size();j++) cur &= b[vec[j]];
      |                            ~~^~~~~~~~~~~~

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