Submission #914477

#	Time	Username	Problem	Language	Result	Execution time	Memory
914477		vjudge1	Council (JOI23_council)	C++17	6 / 100	376 ms	421204 KiB

council

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct trie{
	int s[2];
	int numb=0;
}tre[300000*10];

int bk[90000000];
int n,m;
int c[300100][25],sm[25];
int head=0,prv=0,nxt[300100];
int uct[25];
int cnt=0;

void insert(int which){
	int nw=0;
	for (int i=head;i!=-1;i=nxt[i]){
		int tp=c[which][i];
		if (!tre[nw].s[tp]){
			tre[nw].s[tp]=++cnt;
		}
		//printf("%d %d\n",tp,tre[nw].s[tp]);
		nw=tre[nw].s[tp];
	}
	tre[nw].numb++;
}

int fd(int level,int tnum,int l,int cur,int ult[],int ttn){
	if (l<0){
		return -99999;
	}
	if (level==-1){
	    if (tre[tnum].numb<=1){
	        bool same=true;
    		for (int i=head;i!=-1;i=nxt[i]){
    			if (ult[i]!=c[cur][i]){
    				same=false;
    				break;
    			}
    		}
    		if (same) return -99999;
	    }
		int ans=0;
		for (int i=head;i!=-1;i=nxt[i]){
			if (ult[i]==0&&uct[i]==1){
				ans++;
			}
		}
		if (tre[tnum].numb>1) bk[ttn]=max(bk[ttn],ans);
		return ans;
	}
	int ans=0;
	if (tre[tnum].s[0]){
		ult[level]=0;
		ans=max(ans,fd(nxt[level],tre[tnum].s[0],l,cur,ult,ttn));
	}
	int emmmm=0;
	if (tre[tnum].s[1]){
		ult[level]=1;
		int tp=0;
		if (uct[level]==1){
			emmmm=1;
		}
		tp=fd(nxt[level],tre[tnum].s[1],l-emmmm,cur,ult,ttn);
		ans=max(tp,ans);
	}
	//printf("%d %d %d\n",level,l,ans);
	return ans;
}

int main(){
	memset(bk,0,sizeof bk);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++){
		for (int p=1;p<=m;p++){
			scanf("%d",&c[i][p]);
			sm[p]+=c[i][p];
		}
	}
	int orians=0;
	int mode=0;
	for (int i=1;i<=m;i++){
		if (sm[i]>=(n/2+2)){
			orians++;
		}else if (sm[i]>=n/2){
			if (!head) head=i;
			else nxt[prv]=i;
			prv=i;
			mode++;
		}
	}
	nxt[prv]=-1;
	/*
	for (int i=head;i!=-1;i=nxt[i]){
		printf("%d ",i);
	}
	printf("\n");*/
	for (int i=1;i<=n;i++){
		insert(i);
	}
	//
	//
	for (int i=1;i<=n;i++){
		int ans=0,ct=0;
		int ttn=0;
		memset(uct,0,sizeof uct);
		int tsans=0;
		int cttt=0;
		for (int p=head;p!=-1;p=nxt[p]){
			if (c[i][p]&&sm[p]==(n/2)){
				continue;
			}
			else if (c[i][p]||sm[p]==(n/2)){
				ct++;
				uct[p]=1;
				///
				ttn+=pow(2,cttt)*1;
				///
			}else if (sm[p]>=n/2+1){
				tsans++;
			}
			cttt++;
		}
		int tpans=0;
		if (bk[ttn]){
			tpans=bk[ttn];
		}else{
			for (int p=0;p<=ct;p++){
				int emtary[25];
				memset(emtary,0,sizeof emtary);
				int tps=fd(head,0,p,i,emtary,ttn);
				if (tps>0){
					tpans=tps;
					break;
				}
			}
		}
		//printf("%d %d %d\n",orians,tsans,tpans);
		printf("%d\n",orians+tsans+tpans);
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:107:7: warning: unused variable 'ans' [-Wunused-variable]
  107 |   int ans=0,ct=0;
      |       ^~~
council.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
council.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf("%d",&c[i][p]);
      |    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22