제출 #129184

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

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
const int N = 50*1000+5;
set<int> g[N];
int dp[(1<<11)];
int hv[11][11];
int cl[N];
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;
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(g[i].size()<k && g[i].size()){
            q.push(i);
            cl[i] = 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(!q.size()) break;
        id = q.front();
        q.pop();
        if(!g[id].size()) continue;

        if(id == -1) 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);
        }
        memset(hv,0,sizeof(hv));
        for(int i = 0;i<v.size();i++){
            for(int j = i+1;j<v.size();j++){
                if(g[v[i]].find(v[j])!=g[v[i]].end()){
                    hv[i][j] = hv[j][i] = 1;
                }
            }
        }
        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(!hv[ii][j]){
                            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]));

        }
        for(int i = 0;i<v.size();i++){
            if(g[v[i]].size()<k && !cl[v[i]] && g[v[i]].size()){
                cl[v[i]] = 1;
                q.push(v[i]);
            }
        }
        //if(ans == 1) break;
    }
    cout<<anss<<endl;
    return 0;
}

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

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(g[i].size()<k && g[i].size()){
            ~~~~~~~~~~~^~
politicaldevelopment.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v.size();i++){
                       ~^~~~~~~~~
politicaldevelopment.cpp:62:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = i+1;j<v.size();j++){
                             ~^~~~~~~~~
politicaldevelopment.cpp:70:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<v.size();j++){
                           ~^~~~~~~~~
politicaldevelopment.cpp:73:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int ii = 0;ii<v.size();ii++){
                                ~~^~~~~~~~~
politicaldevelopment.cpp:89:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v.size();i++){
                       ~^~~~~~~~~
politicaldevelopment.cpp:94:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v.size();i++){
                       ~^~~~~~~~~
politicaldevelopment.cpp:95:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(g[v[i]].size()<k && !cl[v[i]] && g[v[i]].size()){
                ~~~~~~~~~~~~~~^~
politicaldevelopment.cpp:12: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: 23 / 23