Submission #971505

#TimeUsernameProblemLanguageResultExecution timeMemory
971505gutzzyPolitical Development (BOI17_politicaldevelopment)C++14
16 / 100
3110 ms338488 KiB
#include <bits/stdc++.h> using namespace std; #define int unsigned short int32_t main(){ int n, k, d, a; cin >> n >> k; vector<vector<bool>> ady(n,vector<bool>(n,0)); set<set<int>> last; vector<int> deg(n,0); for(int i=0;i<n;i++){ last.insert({i}); cin >> d; deg[i] = d; for(int j=0;j<d;j++){ cin >> a; ady[min(i,a)][max(i,a)] = 1; } } int cur = 2; bool optim = false; while(cur<=k){ set<set<int>> nw; for(auto li:last){ if(optim) break; // last[i] --> completed graphs of cur-1 nodes for(int x=0;x<n;x++){ if(deg[x]<cur-1) continue; if (optim) break; bool found = true; for(auto p:li){ if(ady[min(x,p)][max(x,p)]==0){ found = false; break; } } if(found){ set<int> temp = li; temp.insert(x); nw.insert(temp); //for(int kk=0;kk<last[i].size();kk++) cout << last[i][kk] << " "; //cout << x << endl; if(cur==k) optim = true; } } } if(nw.size()==0) break; else{ last = nw; cur++; } } cout << cur-1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...