Submission #203627

#	Time	Username	Problem	Language	Result	Execution time	Memory
203627		karma	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	1053 ms	70288 KiB

politicaldevelopment

#include<bits/stdc++.h>
#define ll            long long
#define pb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair
//#define int           int64_t

using namespace std;

typedef pair<int, int> pii;
const int N = (int)5e4 + 2;

priority_queue<pii, vector<pii>, greater<pii>> pq;
int n, k, d, u, cnt, res, ans;
int deg[N], lab[N], id[N];
bool del[N], ok;
vector<int> adj[N], r[N];
map<pii, bool> edges;
pii top;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define FileName      "test"
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        cin >> d; adj[i].resize(d);
        for(int& c: adj[i]) {
            cin >> c, edges[{i, c}] = 1;
            r[c].pb(i);
        }
        deg[i] = d; pq.push(mp(deg[i], i));
    }
    res = 1;
    while(pq.size()) {
         top = pq.top(); pq.pop();
         if(top.fi != deg[top.se]) continue;
         u = top.se; cnt = 0;
         for(int v: adj[u]) {
             if(del[v] || !edges[{v, u}]) continue;
             id[lab[v] = cnt ++] = v;
         }
         for(int i = 0; i < (1 << cnt); ++i) {
             if((ans = __builtin_popcount(i)) < res) continue;
             ok = 1;
             for(int j = 0; j < cnt; ++j) {
                if(!(i >> j & 1)) continue;
                for(int k = j + 1; k < cnt; ++k) {
                    if((i >> k & 1) && !edges[{id[j], id[k]}]) ok = 0;
                }
                if(!ok) break;
             }
             if(ok) res = ans + 1;
         }
         del[u] = 1;
         for(int v: r[u]) {
            if(del[v]) continue;
            --deg[v]; pq.push(mp(deg[v], v));
         }
    }
    cout << res;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int32_t main()':
politicaldevelopment.cpp:27:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:28:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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