oj.uz

Submission #186884

# Submission time Handle Problem Language Result Execution time Memory
186884 2020-01-12T11:26:53 Z nicolaalexandra Political Development (BOI17_politicaldevelopment) C++14
23 / 100
 536 ms 26144 KB 
#include <bits/stdc++.h>
#define DIM 50010
using namespace std;
priority_queue <pair<int,int>, vector <pair<int,int> >, greater<pair<int,int> > > H;
set <int> L[DIM];
int n,k,i,j,sol,el,nod;
int v[DIM],x[DIM],viz[DIM],f[DIM],g[DIM],mask[DIM];
int verif (int x, int y){
    if (L[x].find(y) != L[x].end())
        return 1;
    return 0;
}

void get_max_clique (int nod){
    el = 0;
    v[++el] = nod;
    mask[1] = (1<<(el-1));
    for (auto vecin:L[nod]){
        v[++el] = vecin;
        mask[el] = (1<<(el-1));
    }
    for (int i=1;i<el;++i)
        for (int j=i+1;j<=el;++j){
            if (i == j){
                mask[i] |= (1<<(i-1));
                continue;
            }
            if (verif(v[i],v[j]))
                mask[i] |= (1<<(j-1));
            if (verif(v[j],v[i]))
                mask[j] |= (1<<(i-1));
        }

    int val = (1<<el)-1;
    for (int i=0;i<=val;++i){
        int ok = 0, nr = 0;
        for (int bit=0;bit<el;++bit){
            if (!(i&(1<<bit))) /// nu face parte din masca
                continue;
            nr++;
            if ((mask[bit+1]&i) != i){ /// nu se potrivesc
                ok = 1;
                break;
            }
        }
        if (!ok)
            sol = max (sol,nr);
    }
}
int main (){

    FILE *fin = stdin;
    FILE *fout = stdout;

    fscanf (fin,"%d%d",&n,&k);
    for (i=1;i<=n;++i){
        fscanf (fin,"%d",&g[i]);
        for (j=1;j<=g[i];++j){
            fscanf (fin,"%d",&nod);
            L[i].insert(nod+1);
        }
        H.push (make_pair(g[i],i));
    }
    while (!H.empty()){
        int nod = H.top().second;
        int grad = H.top().first;
        H.pop();
        if (grad != g[nod]) /// inseamna ca nu e ala cu gradul minim
            continue;
        /// vreau sa gasesc clica maxima din care poate face parte nod
        get_max_clique (nod);
        viz[nod] = 1;
        /// acum il elimin pe nod si toate muchiile
        for (auto vecin:L[nod]){
            if (viz[vecin])
                continue;
            /// nu am incercat sa obtin clica de aici deloc
            viz[vecin] = 1;
            --g[vecin];
            L[vecin].erase(L[vecin].find(nod));
            H.push(make_pair(g[vecin],vecin));

        }
        L[nod].clear();
    }
    fprintf(fout,"%d",sol);

    return 0;
}
/// din nou, nu sunt in stare sa citesc un enunt cum trb

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:55:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:57:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&g[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:59:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&nod);
             ~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 10 ms 3320 KB Output is correct
4 Incorrect 39 ms 3372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 10 ms 3320 KB Output is correct
4 Incorrect 39 ms 3372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2604 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 536 ms 26068 KB Output is correct
12 Correct 4 ms 2756 KB Output is correct
13 Correct 470 ms 25968 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 471 ms 26060 KB Output is correct
16 Correct 462 ms 26100 KB Output is correct
17 Correct 472 ms 26144 KB Output is correct
18 Correct 492 ms 26124 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 10 ms 3320 KB Output is correct
4 Incorrect 39 ms 3372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 10 ms 3320 KB Output is correct
4 Incorrect 39 ms 3372 KB Output isn't correct
5 Halted 0 ms 0 KB -