oj.uz

Submission #486309

# Submission time Handle Problem Language Result Execution time Memory
486309 2021-11-11T08:22:26 Z Koosha_mv Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 505 ms 28084 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]);
			}
		}
	}
	if(v.size()<n){
		while(1){
			v.pb(rand());
		}
	}
	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:103:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  if(v.size()<n){
      |     ~~~~~~~~^~
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++)
......
  109 |  f(t,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:109:2: note: in expansion of macro 'f'
  109 |  f(t,0,v.size()){
      |  ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27724 KB Output is correct
2 Correct 15 ms 27832 KB Output is correct
3 Correct 460 ms 28056 KB Output is correct
4 Correct 505 ms 27980 KB Output is correct
5 Correct 461 ms 27980 KB Output is correct
6 Correct 457 ms 28080 KB Output is correct
7 Correct 466 ms 28084 KB Output is correct
8 Correct 446 ms 27852 KB Output is correct
9 Correct 15 ms 27836 KB Output is correct
10 Correct 432 ms 27888 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27724 KB Output is correct
2 Correct 15 ms 27832 KB Output is correct
3 Correct 460 ms 28056 KB Output is correct
4 Correct 505 ms 27980 KB Output is correct
5 Correct 461 ms 27980 KB Output is correct
6 Correct 457 ms 28080 KB Output is correct
7 Correct 466 ms 28084 KB Output is correct
8 Correct 446 ms 27852 KB Output is correct
9 Correct 15 ms 27836 KB Output is correct
10 Correct 432 ms 27888 KB Output is correct
11 Correct 477 ms 28072 KB Output is correct
12 Correct 484 ms 28072 KB Output is correct
13 Incorrect 16 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 435 ms 27892 KB Output is correct
2 Incorrect 17 ms 27724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27724 KB Output is correct
2 Correct 15 ms 27832 KB Output is correct
3 Correct 460 ms 28056 KB Output is correct
4 Correct 505 ms 27980 KB Output is correct
5 Correct 461 ms 27980 KB Output is correct
6 Correct 457 ms 28080 KB Output is correct
7 Correct 466 ms 28084 KB Output is correct
8 Correct 446 ms 27852 KB Output is correct
9 Correct 15 ms 27836 KB Output is correct
10 Correct 432 ms 27888 KB Output is correct
11 Correct 477 ms 28072 KB Output is correct
12 Correct 484 ms 28072 KB Output is correct
13 Incorrect 16 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 14 ms 27724 KB Output is correct
2 Correct 15 ms 27832 KB Output is correct
3 Correct 460 ms 28056 KB Output is correct
4 Correct 505 ms 27980 KB Output is correct
5 Correct 461 ms 27980 KB Output is correct
6 Correct 457 ms 28080 KB Output is correct
7 Correct 466 ms 28084 KB Output is correct
8 Correct 446 ms 27852 KB Output is correct
9 Correct 15 ms 27836 KB Output is correct
10 Correct 432 ms 27888 KB Output is correct
11 Correct 477 ms 28072 KB Output is correct
12 Correct 484 ms 28072 KB Output is correct
13 Incorrect 16 ms 27724 KB Output isn't correct
14 Halted 0 ms 0 KB -