oj.uz

Submission #486298

# Submission time Handle Problem Language Result Execution time Memory
486298 2021-11-11T08:09:36 Z Koosha_mv Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 24 ms 28236 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;
			}
		}
	}
	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){
	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++)
......
   58 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:58:2: note: in expansion of macro 'f'
   58 |  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++)
......
   61 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:61:2: note: in expansion of macro 'f'
   61 |  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(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:63:3: note: in expansion of macro 'f'
   63 |   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++)
......
   72 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:72:2: note: in expansion of macro 'f'
   72 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:80:7: warning: unused variable 't' [-Wunused-variable]
   80 |   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++)
......
   92 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:92:2: note: in expansion of macro 'f'
   92 |  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++)
......
   95 |   f(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:95:3: note: in expansion of macro 'f'
   95 |   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++)
......
  102 |  f(t,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:102:2: note: in expansion of macro 'f'
  102 |  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 16 ms 27752 KB Output is correct
3 Correct 20 ms 28024 KB Output is correct
4 Correct 19 ms 28160 KB Output is correct
5 Correct 19 ms 28060 KB Output is correct
6 Correct 19 ms 28100 KB Output is correct
7 Correct 24 ms 28236 KB Output is correct
8 Correct 16 ms 27924 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 17 ms 27852 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 16 ms 27752 KB Output is correct
3 Correct 20 ms 28024 KB Output is correct
4 Correct 19 ms 28160 KB Output is correct
5 Correct 19 ms 28060 KB Output is correct
6 Correct 19 ms 28100 KB Output is correct
7 Correct 24 ms 28236 KB Output is correct
8 Correct 16 ms 27924 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 17 ms 27852 KB Output is correct
11 Correct 18 ms 28128 KB Output is correct
12 Correct 18 ms 28100 KB Output is correct
13 Incorrect 15 ms 27756 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27900 KB Output is correct
2 Incorrect 15 ms 27828 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 16 ms 27752 KB Output is correct
3 Correct 20 ms 28024 KB Output is correct
4 Correct 19 ms 28160 KB Output is correct
5 Correct 19 ms 28060 KB Output is correct
6 Correct 19 ms 28100 KB Output is correct
7 Correct 24 ms 28236 KB Output is correct
8 Correct 16 ms 27924 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 17 ms 27852 KB Output is correct
11 Correct 18 ms 28128 KB Output is correct
12 Correct 18 ms 28100 KB Output is correct
13 Incorrect 15 ms 27756 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 16 ms 27752 KB Output is correct
3 Correct 20 ms 28024 KB Output is correct
4 Correct 19 ms 28160 KB Output is correct
5 Correct 19 ms 28060 KB Output is correct
6 Correct 19 ms 28100 KB Output is correct
7 Correct 24 ms 28236 KB Output is correct
8 Correct 16 ms 27924 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 17 ms 27852 KB Output is correct
11 Correct 18 ms 28128 KB Output is correct
12 Correct 18 ms 28100 KB Output is correct
13 Incorrect 15 ms 27756 KB Output isn't correct
14 Halted 0 ms 0 KB -