제출 #727973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727973		_martynas	Political Development (BOI17_politicaldevelopment)	C++11	100 / 100	666 ms	314220 KiB

politicaldevelopment

/*
"For any non-empty group of party members, there is always
at least one member of the group who disagrees with (strictly)
less than K of the other group members."
1. Apply this condition to all of the nodes ->
there is at least one node with degree < K
2. Apply condition to everything except the min degree
node and its edges -> again, there is at least one node with degree < K

*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MXN = 50005;

int n, k;
int deg[MXN];
vi adj[MXN];
bool visited[MXN];
bitset<1LL*MXN*MXN> E;

int main() {
    cin >> n >> k;
    queue<int> Q;
    for(int i = 0; i < n; i++) {
        cin >> deg[i];
        for(int j = 0; j < deg[i]; j++) {
            int a; cin >> a; adj[i].PB(a);
            E[1LL*i*n+a] = 1;
        }
    }
    for(int i = 0; i < n; i++) if(deg[i] < k) Q.push(i);
    int mx = 1;
    while(!Q.empty()) {
        int a = Q.front(); Q.pop();
        visited[a] = true;
        vi arr;
        for(int b : adj[a]) if(!visited[b]) arr.PB(b);
        for(int mask = 0; mask < (1 << arr.size()); mask++) {
            bool ok = true;
            for(int i = 0; i < arr.size(); i++) {
                if(~mask & (1 << i)) continue;
                for(int j = 0; j < i; j++) {
                    if(~mask & (1 << j)) continue;
                    if(!E[1LL*arr[i]*n+arr[j]]) ok = false;
                }
            }
            if(ok) mx = max(mx, __builtin_popcount(mask)+1);
        }
        for(int b : adj[a]) {
            if(deg[b] == k) Q.push(b);
            deg[b]--;
        }
    }
    cout << mx << "\n";
    return 0;
}

/*



*/

컴파일 시 표준 에러 (stderr) 메시지

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int i = 0; i < arr.size(); i++) {
      |                            ~~^~~~~~~~~~~~

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