oj.uz

Submission #486303

# Submission time Handle Problem Language Result Execution time Memory
486303 2021-11-11T08:15:44 Z Koosha_mv Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 598 ms 28096 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){
	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++)
......
   59 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:59:2: note: in expansion of macro 'f'
   59 |  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++)
......
   62 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:62:2: note: in expansion of macro 'f'
   62 |  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++)
......
   64 |   f(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:64:3: note: in expansion of macro 'f'
   64 |   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++)
......
   73 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:73:2: note: in expansion of macro 'f'
   73 |  f(i,0,v.size()){
      |  ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:81:7: warning: unused variable 't' [-Wunused-variable]
   81 |   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++)
......
   93 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:93:2: note: in expansion of macro 'f'
   93 |  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++)
......
   96 |   f(j,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
politicaldevelopment.cpp:96:3: note: in expansion of macro 'f'
   96 |   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++)
......
  103 |  f(t,0,v.size()){
      |    ~~~~~~~~~~~~                
politicaldevelopment.cpp:103:2: note: in expansion of macro 'f'
  103 |  f(t,0,v.size()){
      |  ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27724 KB Output is correct
2 Correct 16 ms 27792 KB Output is correct
3 Correct 455 ms 28052 KB Output is correct
4 Correct 438 ms 28072 KB Output is correct
5 Correct 468 ms 27980 KB Output is correct
6 Correct 451 ms 28032 KB Output is correct
7 Correct 455 ms 28096 KB Output is correct
8 Correct 546 ms 27888 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 446 ms 27892 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27724 KB Output is correct
2 Correct 16 ms 27792 KB Output is correct
3 Correct 455 ms 28052 KB Output is correct
4 Correct 438 ms 28072 KB Output is correct
5 Correct 468 ms 27980 KB Output is correct
6 Correct 451 ms 28032 KB Output is correct
7 Correct 455 ms 28096 KB Output is correct
8 Correct 546 ms 27888 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 446 ms 27892 KB Output is correct
11 Correct 466 ms 28072 KB Output is correct
12 Correct 465 ms 28076 KB Output is correct
13 Incorrect 20 ms 27836 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 27892 KB Output is correct
2 Incorrect 19 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 19 ms 27724 KB Output is correct
2 Correct 16 ms 27792 KB Output is correct
3 Correct 455 ms 28052 KB Output is correct
4 Correct 438 ms 28072 KB Output is correct
5 Correct 468 ms 27980 KB Output is correct
6 Correct 451 ms 28032 KB Output is correct
7 Correct 455 ms 28096 KB Output is correct
8 Correct 546 ms 27888 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 446 ms 27892 KB Output is correct
11 Correct 466 ms 28072 KB Output is correct
12 Correct 465 ms 28076 KB Output is correct
13 Incorrect 20 ms 27836 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27724 KB Output is correct
2 Correct 16 ms 27792 KB Output is correct
3 Correct 455 ms 28052 KB Output is correct
4 Correct 438 ms 28072 KB Output is correct
5 Correct 468 ms 27980 KB Output is correct
6 Correct 451 ms 28032 KB Output is correct
7 Correct 455 ms 28096 KB Output is correct
8 Correct 546 ms 27888 KB Output is correct
9 Correct 16 ms 27724 KB Output is correct
10 Correct 446 ms 27892 KB Output is correct
11 Correct 466 ms 28072 KB Output is correct
12 Correct 465 ms 28076 KB Output is correct
13 Incorrect 20 ms 27836 KB Output isn't correct
14 Halted 0 ms 0 KB -