제출 #129172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129172		Vardanyan	Political Development (BOI17_politicaldevelopment)	C++14	77 / 100	3026 ms	26592 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
const int N = 50*1000+5;
set<int> g[N];
int dp[(1<<11)];

int main(){
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int x;
    for(int i = 0;i<n;i++){

        int q;
        cin>>q;
        while(q--){
            int x;
            cin>>x;
            g[i].insert(x);
        }
    }
    int anss = 1;
    while(1){
            memset(dp,0,sizeof(dp));
        int id = -1;
        for(int i = 0;i<n;i++){
            if(g[i].size()<k && g[i].size()){
                id = i;
                break;
            }
        }
        if(id == -1) break;
        /*if(sz == 1){
            anss = max(anss,sz+1);
            break;
        }*/
        vector<int> v;
        set<int>::iterator it;
        int ans = 1;
        for(it = g[id].begin();it!=g[id].end();++it){
            int to = *it;
            v.push_back(to);
            dp[(1<<(v.size()-1))] = 1;
            anss = max(anss,2);
        }
        for(int i = 1;i<(1<<v.size());i++){
            if(!dp[i]) continue;
            for(int j = 0;j<v.size();j++){
                if((i>>j)&1 ) continue;
                bool f = true;
                for(int ii = 0;ii<v.size();ii++){
                    if((i>>ii)&1){
                        if(g[v[ii]].find(v[j])==g[v[ii]].end()){
                            f = false;
                            break;
                        }
                    }
                }
                if(f){
                    dp[i|(1<<j)] = max(dp[i|(1<<j)],dp[i]+1);
                    ans = max(ans,dp[i]+1);
                }
            }
        }
        anss = max(ans+1,anss);
      //  cout<<ans<<endl;
        for(int i = 0;i<v.size();i++){
            g[v[i]].erase(g[v[i]].find(id));
            g[id].erase(g[id].find(v[i]));
        }
        //if(ans == 1) break;
    }
    cout<<anss<<endl;
    return 0;
}

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

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:27:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(g[i].size()<k && g[i].size()){
                ~~~~~~~~~~~^~
politicaldevelopment.cpp:48:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<v.size();j++){
                           ~^~~~~~~~~
politicaldevelopment.cpp:51:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int ii = 0;ii<v.size();ii++){
                                ~~^~~~~~~~~
politicaldevelopment.cpp:67:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v.size();i++){
                       ~^~~~~~~~~
politicaldevelopment.cpp:11:9: warning: unused variable 'x' [-Wunused-variable]
     int x;
         ^

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