oj.uz

답안 #203626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203626 2020-02-21T16:27:50 Z karma Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 16 ms 3832 KB 
#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], f[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 = 1; 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]) 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 << min(res, k);
}

Compilation message

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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2684 KB Output is correct
3 Correct 13 ms 3704 KB Output is correct
4 Correct 16 ms 3832 KB Output is correct
5 Correct 12 ms 3832 KB Output is correct
6 Correct 12 ms 3832 KB Output is correct
7 Correct 12 ms 3832 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 6 ms 2680 KB Output is correct
10 Incorrect 7 ms 2808 KB Output isn't correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2684 KB Output is correct
3 Correct 13 ms 3704 KB Output is correct
4 Correct 16 ms 3832 KB Output is correct
5 Correct 12 ms 3832 KB Output is correct
6 Correct 12 ms 3832 KB Output is correct
7 Correct 12 ms 3832 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 6 ms 2680 KB Output is correct
10 Incorrect 7 ms 2808 KB Output isn't correct

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Incorrect 6 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2684 KB Output is correct
3 Correct 13 ms 3704 KB Output is correct
4 Correct 16 ms 3832 KB Output is correct
5 Correct 12 ms 3832 KB Output is correct
6 Correct 12 ms 3832 KB Output is correct
7 Correct 12 ms 3832 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 6 ms 2680 KB Output is correct
10 Incorrect 7 ms 2808 KB Output isn't correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2684 KB Output is correct
3 Correct 13 ms 3704 KB Output is correct
4 Correct 16 ms 3832 KB Output is correct
5 Correct 12 ms 3832 KB Output is correct
6 Correct 12 ms 3832 KB Output is correct
7 Correct 12 ms 3832 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 6 ms 2680 KB Output is correct
10 Incorrect 7 ms 2808 KB Output isn't correct