# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129152 | 2019-07-11T18:17:29 Z | davitmarg | Political Development (BOI17_politicaldevelopment) | C++17 | 117 ms | 1912 KB |
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <set> #include <queue> #include <iomanip> #include <stack> #include <cassert> #include <iterator> #include <bitset> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(),v.end() using namespace std; int n,k,used[50004],c[(1<<11)+5],ind[50004],s[50004],f[(1<<11)+5],ans=1; vector<int> g[50004]; queue<int> q; int main() { cin>>n>>k; for(int i=0;i<n;i++) { int d,x; cin>>d; for(int j=0;j<d;j++) { scanf("%d",&x); g[i].PB(x); } s[i]=g[i].size(); } for(int i=1;i<(1<<k);i++) for(int j=0;j<k;j++) if(((1<<j)&i)) { c[i]++; f[i]=j; } for(int i=0;i<n;i++) if(s[i]<k) q.push(i); while(!q.empty()) { int v=q.front(); q.pop(); if(used[v]) continue; used[v]=1; vector<int> a,mask; for(int i=0;i<g[v].size();i++) { int to=g[v][i]; if(!used[to]) a.PB(to); s[to]--; if(s[to]<k) q.push(to); } mask.resize(a.size(),0); for(int i=0;i<a.size();i++) ind[a[i]]=i; for(int i=0;i<a.size();i++) { for(int j=0;j<g[a[i]].size();j++) { int to=g[a[i]][j]; if(used[to]) continue; mask[i]+=(1<<ind[to]); } } vector<bool> dp((1<<a.size())+10); dp[0]=1; for(int m=1;m<(1<<a.size());m++) { int bit=f[m]; int y=m-(1<<bit); if( (mask[bit]&y)==y && dp[y]) { dp[m]=1; ans=max(ans,c[m]+1); } } } cout<<ans<<endl; return 0; } /* 4 2 2 1 4 2 0 2 2 2 4 0 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 3 ms | 1528 KB | Output is correct |
3 | Correct | 8 ms | 1784 KB | Output is correct |
4 | Correct | 117 ms | 1784 KB | Output is correct |
5 | Correct | 117 ms | 1788 KB | Output is correct |
6 | Correct | 9 ms | 1784 KB | Output is correct |
7 | Correct | 9 ms | 1784 KB | Output is correct |
8 | Correct | 4 ms | 1528 KB | Output is correct |
9 | Correct | 3 ms | 1528 KB | Output is correct |
10 | Correct | 4 ms | 1528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 3 ms | 1528 KB | Output is correct |
3 | Correct | 8 ms | 1784 KB | Output is correct |
4 | Correct | 117 ms | 1784 KB | Output is correct |
5 | Correct | 117 ms | 1788 KB | Output is correct |
6 | Correct | 9 ms | 1784 KB | Output is correct |
7 | Correct | 9 ms | 1784 KB | Output is correct |
8 | Correct | 4 ms | 1528 KB | Output is correct |
9 | Correct | 3 ms | 1528 KB | Output is correct |
10 | Correct | 4 ms | 1528 KB | Output is correct |
11 | Correct | 114 ms | 1912 KB | Output is correct |
12 | Correct | 117 ms | 1784 KB | Output is correct |
13 | Incorrect | 3 ms | 1532 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1528 KB | Output is correct |
2 | Incorrect | 3 ms | 1528 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 3 ms | 1528 KB | Output is correct |
3 | Correct | 8 ms | 1784 KB | Output is correct |
4 | Correct | 117 ms | 1784 KB | Output is correct |
5 | Correct | 117 ms | 1788 KB | Output is correct |
6 | Correct | 9 ms | 1784 KB | Output is correct |
7 | Correct | 9 ms | 1784 KB | Output is correct |
8 | Correct | 4 ms | 1528 KB | Output is correct |
9 | Correct | 3 ms | 1528 KB | Output is correct |
10 | Correct | 4 ms | 1528 KB | Output is correct |
11 | Correct | 114 ms | 1912 KB | Output is correct |
12 | Correct | 117 ms | 1784 KB | Output is correct |
13 | Incorrect | 3 ms | 1532 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 3 ms | 1528 KB | Output is correct |
3 | Correct | 8 ms | 1784 KB | Output is correct |
4 | Correct | 117 ms | 1784 KB | Output is correct |
5 | Correct | 117 ms | 1788 KB | Output is correct |
6 | Correct | 9 ms | 1784 KB | Output is correct |
7 | Correct | 9 ms | 1784 KB | Output is correct |
8 | Correct | 4 ms | 1528 KB | Output is correct |
9 | Correct | 3 ms | 1528 KB | Output is correct |
10 | Correct | 4 ms | 1528 KB | Output is correct |
11 | Correct | 114 ms | 1912 KB | Output is correct |
12 | Correct | 117 ms | 1784 KB | Output is correct |
13 | Incorrect | 3 ms | 1532 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |