oj.uz

Submission #486307

# Submission time Handle Problem Language Result Execution time Memory
486307 2021-11-11T08:20:47 Z Koosha_mv Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 576 ms 28108 KB 
#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99,K=15;

int n,k,ans,a[N],mark[N],deg[N],fb[(1<<K)],dp[(1<<K)],adj[K];
vector<int> v,g[N];

void make(){
	f(i,0,n){
		vector<int> v;
		f(j,0,g[i].size()){
			if(mark[i]<mark[g[i][j]]){
				v.pb(g[i][j]);
			}
		}
		g[i]=v;
	}
	f(mask,1,(1<<K)){
		f(i,0,K){
			if(mask&(1<<i)){
				fb[mask]=i;
			}
		}
		//cout<<mask<<" : "<<fb[mask]<<endl;
	}
	fill(mark,mark+N,-1);
}
void max_ind(int n){
	dp[0]=1;
	f(mask,1,(1<<n)){
		int u=fb[mask];
		dp[mask]=(dp[mask^(1<<u)] && (adj[u]&mask)==0);
		if(dp[mask]){
			maxm(ans,nb(mask));
		}
	}
}
void solve(vector<int> v){
	fill(mark,mark+N,-1);
	f(i,0,K){
		adj[i]=0;
	}
	f(i,0,v.size()){
		mark[v[i]]=i;
	}
	f(i,0,v.size()){
		int u=v[i];
		f(j,0,g[u].size()){
			if(mark[g[u][j]]!=-1){
				int _u=mark[u],_v=mark[g[u][j]];
				adj[_u]|=(1<<_v);
				adj[_v]|=(1<<_u);
			}
		}
	}
	max_ind(v.size());
	f(i,0,v.size()){
		mark[v[i]]=-1;
	}
}

int main(){
	cin>>n>>k;
	f(i,0,n){
		int t,x;
		cin>>deg[i];
		f(j,0,deg[i]){
			cin>>x;
			g[i].pb(x);
		}
	}
	f(i,0,n){
		if(deg[i]<k){
			v.pb(i);
		}
	}
	f(i,0,v.size()){
		int u=v[i];
		mark[u]=i;
		f(j,0,g[u].size()){
			if(--deg[g[u][j]]==k-1){
				v.pb(g[u][j]);
			}
		}
	}
	make();
	f(t,0,v.size()){
		int u=v[t];
		solve(g[u]);
	}
	cout<<ans+1;
}

Compilation message

politicaldevelopment.cpp: In function 'void make()':
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   28 |   f(j,0,g[i].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:28:3: note: in expansion of macro 'f'
   28 |   f(j,0,g[i].size()){
      |   ^
politicaldevelopment.cpp: In function 'void solve(std::vector<int>)':
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   60 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:60:2: note: in expansion of macro 'f'
   60 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   63 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:63:2: note: in expansion of macro 'f'
   63 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   65 |   f(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:65:3: note: in expansion of macro 'f'
   65 |   f(j,0,g[u].size()){
      |   ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   74 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:74:2: note: in expansion of macro 'f'
   74 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:82:7: warning: unused variable 't' [-Wunused-variable]
   82 |   int t,x;
      |       ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   94 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:94:2: note: in expansion of macro 'f'
   94 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   97 |   f(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:97:3: note: in expansion of macro 'f'
   97 |   f(j,0,g[u].size()){
      |   ^
politicaldevelopment.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  104 |  f(t,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:104:2: note: in expansion of macro 'f'
  104 |  f(t,0,v.size()){
      |  ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27724 KB Output is correct
2 Correct 19 ms 27816 KB Output is correct
3 Correct 472 ms 28048 KB Output is correct
4 Correct 498 ms 28076 KB Output is correct
5 Correct 576 ms 28068 KB Output is correct
6 Correct 478 ms 28084 KB Output is correct
7 Correct 450 ms 28108 KB Output is correct
8 Correct 487 ms 27852 KB Output is correct
9 Correct 14 ms 27724 KB Output is correct
10 Correct 463 ms 27908 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27724 KB Output is correct
2 Correct 19 ms 27816 KB Output is correct
3 Correct 472 ms 28048 KB Output is correct
4 Correct 498 ms 28076 KB Output is correct
5 Correct 576 ms 28068 KB Output is correct
6 Correct 478 ms 28084 KB Output is correct
7 Correct 450 ms 28108 KB Output is correct
8 Correct 487 ms 27852 KB Output is correct
9 Correct 14 ms 27724 KB Output is correct
10 Correct 463 ms 27908 KB Output is correct
11 Correct 509 ms 28108 KB Output is correct
12 Correct 471 ms 28072 KB Output is correct
13 Incorrect 15 ms 27724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 27892 KB Output is correct
2 Incorrect 16 ms 27820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27724 KB Output is correct
2 Correct 19 ms 27816 KB Output is correct
3 Correct 472 ms 28048 KB Output is correct
4 Correct 498 ms 28076 KB Output is correct
5 Correct 576 ms 28068 KB Output is correct
6 Correct 478 ms 28084 KB Output is correct
7 Correct 450 ms 28108 KB Output is correct
8 Correct 487 ms 27852 KB Output is correct
9 Correct 14 ms 27724 KB Output is correct
10 Correct 463 ms 27908 KB Output is correct
11 Correct 509 ms 28108 KB Output is correct
12 Correct 471 ms 28072 KB Output is correct
13 Incorrect 15 ms 27724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27724 KB Output is correct
2 Correct 19 ms 27816 KB Output is correct
3 Correct 472 ms 28048 KB Output is correct
4 Correct 498 ms 28076 KB Output is correct
5 Correct 576 ms 28068 KB Output is correct
6 Correct 478 ms 28084 KB Output is correct
7 Correct 450 ms 28108 KB Output is correct
8 Correct 487 ms 27852 KB Output is correct
9 Correct 14 ms 27724 KB Output is correct
10 Correct 463 ms 27908 KB Output is correct
11 Correct 509 ms 28108 KB Output is correct
12 Correct 471 ms 28072 KB Output is correct
13 Incorrect 15 ms 27724 KB Output isn't correct
14 Halted 0 ms 0 KB -