oj.uz

Submission #851090

# Submission time Handle Problem Language Result Execution time Memory
851090 2023-09-18T13:44:48 Z kderylo Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 6 ms 4004 KB 
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int stala=5e4+10;
const int st=(1<<12);
vector<int>w[stala];
vector<int>odw_w[stala];
int deg[stala];
set<pair<int,int> >s;
set<pair<int,int> >krawedzie;
vector<int>pom;
int tab[st];
int number_of_bits(int ile,int dl)
{
    int wyn=0;
    for(int i=0;i<dl;i++){
        if((ile&(1<<i))>0){
            wyn++;
        }
    }
    return wyn;
}
int find_subset()
{
    int dl=(int)pom.size();
    int wyn=0;
    for(int i=0;i<dl;i++){
        tab[(1<<i)]=1;
        for(int j=i+1;j<dl;j++){
            int x=((1<<i)|(1<<j));
            if(krawedzie.find({pom[i],pom[j]})!=krawedzie.end()&&krawedzie.find({pom[j],pom[i]})!=krawedzie.end()){
                tab[x]=1;
            }
        }
    }
    for(int i=0;i<(1<<dl);i++){
        if(tab[i]!=1){
            tab[i]=1;
            for(int j=0;j<dl;j++){
                if((i&(1<<j))>0){
                    tab[i]&=(tab[i-(1<<j)]);
                }
            }
        }
        if(tab[i]==1){
            wyn=max(wyn,number_of_bits(i,dl));
        }
    }
    for(int i=0;i<(1<<dl);i++){
        tab[i]=0;
    }
    return wyn;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,k;
    cin>>ile>>k;
    for(int i=0;i<ile;i++){
        int il;
        cin>>il;
        for(int j=0;j<il;j++){
            int a;
            cin>>a;
            deg[i]++;
            w[i].push_back(a);
            odw_w[a].push_back(i);
            krawedzie.insert({i,a});
        }
    }
    int wyn=0;
    for(int i=0;i<ile;i++){
        s.insert({deg[i],i});
    }
    for(int i=0;i<ile;i++){
        int x=s.begin()->second;
        deg[x]=-1;
        s.erase(s.begin());
        for(int j=0;j<(int)odw_w[x].size();j++){
            int wie=odw_w[x][j];
            int de=deg[wie];
            s.erase({de,wie});
            de--;
            s.insert({de,wie});
        }
        pom.clear();
        pom.push_back(x);
        for(int j=0;j<(int)w[x].size();j++){
            if(deg[w[x][j]]!=-1){
                pom.push_back(w[x][j]);
            }
        }
        wyn=max(wyn,find_subset());
    }
    cout<<wyn;

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 5 ms 3928 KB Output is correct
7 Correct 5 ms 3932 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 5 ms 3928 KB Output is correct
7 Correct 5 ms 3932 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 5 ms 4004 KB Output is correct
12 Correct 5 ms 3932 KB Output is correct
13 Incorrect 1 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3116 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 5 ms 3928 KB Output is correct
7 Correct 5 ms 3932 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 5 ms 4004 KB Output is correct
12 Correct 5 ms 3932 KB Output is correct
13 Incorrect 1 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 5 ms 3928 KB Output is correct
7 Correct 5 ms 3932 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 5 ms 4004 KB Output is correct
12 Correct 5 ms 3932 KB Output is correct
13 Incorrect 1 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -