oj.uz

Submission #244620

# Submission time Handle Problem Language Result Execution time Memory
244620 2020-07-04T12:34:53 Z kimbj0709 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 3000 ms 24312 KB 
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 50050
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_people,k;
    int no_of_input1;
    int input;
    cin >> no_of_people >> k;
    vector<unordered_set<int> > adj(maxn);
    bool can2 = 0;
    for(int i=0;i<no_of_people;i++){
        cin >> no_of_input1;
        for(int j=0;j<no_of_input1;j++){
            cin >> input;
            adj[i].insert(input);
        }
    }
    int ans = 1;
    for(int i=0;i<no_of_people;i++){
        for(int j=0;j<pow(2,adj[i].size());j++){
            vector<int> temp;
            if(__builtin_popcount(j)>=k||__builtin_popcount(j)+1<=ans){
                continue;
            }
            int cnt = 0;
            for(auto kk:adj[i]){
                if(j&(1<<cnt)){
                    temp.push_back(kk);
                }
                cnt++;
            }
            temp.push_back(i);
            /*for(auto kk:temp){
                cout << kk << " ";
            }
            cout << "\n---------\n";*/
            for(int a=0;a<temp.size();a++){
                for(int b=0;b<temp.size();b++){
                    if(a==b){
                        continue;
                    }
                    if(adj[temp[a]].count(temp[b])==0){
                        goto cont;
                    }
                }
            }
            //cout << "YES" << " " << temp.size() << "\n";
            ans = max(ans,(int)temp.size());
            cont : ;
        }

    }
    cout << min(k,ans);

}

Compilation message

politicaldevelopment.cpp: In function 'int32_t main()':
politicaldevelopment.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int a=0;a<temp.size();a++){
                         ~^~~~~~~~~~~~
politicaldevelopment.cpp:41:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int b=0;b<temp.size();b++){
                             ~^~~~~~~~~~~~
politicaldevelopment.cpp:13:10: warning: unused variable 'can2' [-Wunused-variable]
     bool can2 = 0;
          ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 13 ms 3584 KB Output is correct
4 Execution timed out 3087 ms 3584 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 13 ms 3584 KB Output is correct
4 Execution timed out 3087 ms 3584 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB Output is correct
2 Correct 7 ms 3072 KB Output is correct
3 Correct 6 ms 3072 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct
5 Correct 7 ms 3200 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 6 ms 3072 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Execution timed out 3095 ms 24312 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 13 ms 3584 KB Output is correct
4 Execution timed out 3087 ms 3584 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 13 ms 3584 KB Output is correct
4 Execution timed out 3087 ms 3584 KB Time limit exceeded
5 Halted 0 ms 0 KB -