Submission #163370

#	Time	Username	Problem	Language	Result	Execution time	Memory
163370		Minnakhmetov	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	351 ms	215268 KiB

politicaldevelopment

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 5e4 + 5, K = 10;
vector<int> g[N], cand[N], anime[N];
int deg[N], dp[N][1 << K], sz[1 << K];
bool used[N], killed[N], on[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
    	cin >> deg[i];
    	for (int j = 0; j < deg[i]; j++) {
    		int x;
    		cin >> x;
    		g[i].push_back(x);
    	}
    }

    queue<int> q;

    for (int i = 0; i < n; i++) {
    	if (deg[i] < k) {
    		used[i] = 1;
    		q.push(i);
    	}
    }

    while (!q.empty()) {
    	int node = q.front();
    	q.pop();

    	killed[node] = 1;

    	for (int to : g[node]) {
    		if (!used[to]) {
    			deg[to]--;
    			if (deg[to] < k) {
    				used[to] = 1;
    				q.push(to);
    			}
    		}
    	}

    	for (int to : g[node]) {
    		if (!killed[to]) {
    			anime[to].push_back(node);
    			cand[node].push_back(to);
    		}
    	}

    	sort(all(cand[node]));

    	// cout << node << " : ";
    	// for (int x : cand[node])
    	// 	cout << x << " ";
    	// cout << "\n";
    }

    for (int i = 0; i < n; i++) {
    	for (int to : g[i]) {
    		on[to] = 1;
    	}
    	on[i] = 1;

    	for (int to : anime[i]) {
    		int m = 0, x;

    		for (int j = 0; j < cand[to].size(); j++) {
    			if (on[cand[to][j]]) {
    				m |= 1 << j;
    			}
    			if (cand[to][j] == i)
    				x = j;
    		}

    		// cout << (1 << x) << " " << m << "\n";

    		dp[to][1 << x] = m;
    	}

    	for (int to : g[i]) {
    		on[to] = 0;
    	}
    	on[i] = 0;
    }

    for (int i = 0; i < (1 << K); i++)
    	sz[i] = __builtin_popcount(i);

    int ans = 1;

    for (int i = 0; i < n; i++) {
    	int len = cand[i].size();

    	dp[i][0] = (1 << len) - 1;

    	for (int j = 1; j < (1 << len); j++) {
    		dp[i][j] = (dp[i][j & -j] & dp[i][j ^ (j & -j)]);


    		if (j == dp[i][j])
    			ans = max(ans, sz[j] + 1);
    	}
    }

    cout << ans;

    return 0;
} 

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:78:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < cand[to].size(); j++) {
                       ~~^~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:88:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
       dp[to][1 << x] = m;
              ~~^~~~

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