답안 #914477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914477	2024-01-22T08:46:47 Z	vjudge1	Council (JOI23_council)	C++17	6 / 100	376 ms	421204 KB

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

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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	389456 KB	Output is correct
2	Correct	93 ms	389460 KB	Output is correct
3	Correct	89 ms	389320 KB	Output is correct
4	Correct	92 ms	389448 KB	Output is correct
5	Correct	89 ms	389460 KB	Output is correct
6	Correct	92 ms	389460 KB	Output is correct
7	Correct	92 ms	389792 KB	Output is correct
8	Correct	93 ms	389460 KB	Output is correct
9	Correct	92 ms	389516 KB	Output is correct
10	Correct	92 ms	389456 KB	Output is correct
11	Correct	92 ms	389416 KB	Output is correct
12	Correct	96 ms	389456 KB	Output is correct
13	Correct	91 ms	389312 KB	Output is correct
14	Correct	95 ms	389456 KB	Output is correct
15	Correct	93 ms	389456 KB	Output is correct
16	Correct	92 ms	389460 KB	Output is correct
17	Correct	94 ms	389460 KB	Output is correct
18	Correct	93 ms	389396 KB	Output is correct
19	Correct	90 ms	389456 KB	Output is correct
20	Correct	95 ms	389528 KB	Output is correct
21	Correct	91 ms	389524 KB	Output is correct
22	Correct	89 ms	389488 KB	Output is correct
23	Correct	89 ms	389456 KB	Output is correct
24	Correct	93 ms	389684 KB	Output is correct
25	Correct	92 ms	389460 KB	Output is correct
26	Correct	93 ms	389504 KB	Output is correct
27	Correct	91 ms	389324 KB	Output is correct
28	Correct	90 ms	389460 KB	Output is correct
29	Correct	91 ms	389428 KB	Output is correct
30	Correct	90 ms	389456 KB	Output is correct
31	Correct	91 ms	389380 KB	Output is correct
32	Correct	94 ms	389460 KB	Output is correct
33	Correct	100 ms	389632 KB	Output is correct
34	Correct	93 ms	389460 KB	Output is correct
35	Correct	92 ms	389500 KB	Output is correct
36	Correct	93 ms	389400 KB	Output is correct
37	Incorrect	93 ms	389472 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	389456 KB	Output is correct
2	Correct	93 ms	389460 KB	Output is correct
3	Correct	89 ms	389320 KB	Output is correct
4	Correct	92 ms	389448 KB	Output is correct
5	Correct	89 ms	389460 KB	Output is correct
6	Correct	92 ms	389460 KB	Output is correct
7	Correct	92 ms	389792 KB	Output is correct
8	Correct	93 ms	389460 KB	Output is correct
9	Correct	92 ms	389516 KB	Output is correct
10	Correct	92 ms	389456 KB	Output is correct
11	Correct	92 ms	389416 KB	Output is correct
12	Correct	96 ms	389456 KB	Output is correct
13	Correct	91 ms	389312 KB	Output is correct
14	Correct	95 ms	389456 KB	Output is correct
15	Correct	93 ms	389456 KB	Output is correct
16	Correct	92 ms	389460 KB	Output is correct
17	Correct	94 ms	389460 KB	Output is correct
18	Correct	93 ms	389396 KB	Output is correct
19	Correct	90 ms	389456 KB	Output is correct
20	Correct	95 ms	389528 KB	Output is correct
21	Correct	91 ms	389524 KB	Output is correct
22	Correct	89 ms	389488 KB	Output is correct
23	Correct	89 ms	389456 KB	Output is correct
24	Correct	93 ms	389684 KB	Output is correct
25	Correct	92 ms	389460 KB	Output is correct
26	Correct	93 ms	389504 KB	Output is correct
27	Correct	91 ms	389324 KB	Output is correct
28	Correct	90 ms	389460 KB	Output is correct
29	Correct	91 ms	389428 KB	Output is correct
30	Correct	90 ms	389456 KB	Output is correct
31	Correct	91 ms	389380 KB	Output is correct
32	Correct	94 ms	389460 KB	Output is correct
33	Correct	100 ms	389632 KB	Output is correct
34	Correct	93 ms	389460 KB	Output is correct
35	Correct	92 ms	389500 KB	Output is correct
36	Correct	93 ms	389400 KB	Output is correct
37	Incorrect	93 ms	389472 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #3

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	389456 KB	Output is correct
2	Correct	165 ms	418424 KB	Output is correct
3	Correct	177 ms	418384 KB	Output is correct
4	Correct	154 ms	418232 KB	Output is correct
5	Correct	167 ms	418384 KB	Output is correct
6	Correct	156 ms	418252 KB	Output is correct
7	Correct	174 ms	418388 KB	Output is correct
8	Correct	91 ms	389460 KB	Output is correct
9	Correct	92 ms	389456 KB	Output is correct
10	Correct	95 ms	389404 KB	Output is correct
11	Correct	91 ms	389500 KB	Output is correct
12	Correct	92 ms	389532 KB	Output is correct
13	Correct	93 ms	389512 KB	Output is correct
14	Correct	89 ms	389336 KB	Output is correct
15	Correct	91 ms	389460 KB	Output is correct
16	Correct	90 ms	389460 KB	Output is correct
17	Correct	90 ms	389712 KB	Output is correct

Subtask #4

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	389456 KB	Output is correct
2	Correct	165 ms	418424 KB	Output is correct
3	Correct	177 ms	418384 KB	Output is correct
4	Correct	154 ms	418232 KB	Output is correct
5	Correct	167 ms	418384 KB	Output is correct
6	Correct	156 ms	418252 KB	Output is correct
7	Correct	174 ms	418388 KB	Output is correct
8	Correct	91 ms	389460 KB	Output is correct
9	Correct	92 ms	389456 KB	Output is correct
10	Correct	95 ms	389404 KB	Output is correct
11	Correct	91 ms	389500 KB	Output is correct
12	Correct	92 ms	389532 KB	Output is correct
13	Correct	93 ms	389512 KB	Output is correct
14	Correct	89 ms	389336 KB	Output is correct
15	Correct	91 ms	389460 KB	Output is correct
16	Correct	90 ms	389460 KB	Output is correct
17	Correct	90 ms	389712 KB	Output is correct
18	Correct	92 ms	389432 KB	Output is correct
19	Correct	92 ms	389512 KB	Output is correct
20	Correct	340 ms	420880 KB	Output is correct
21	Correct	321 ms	420572 KB	Output is correct
22	Correct	321 ms	420584 KB	Output is correct
23	Correct	294 ms	421204 KB	Output is correct
24	Correct	294 ms	420692 KB	Output is correct
25	Correct	300 ms	420796 KB	Output is correct
26	Correct	376 ms	420800 KB	Output is correct
27	Correct	91 ms	389460 KB	Output is correct
28	Correct	96 ms	389708 KB	Output is correct
29	Correct	92 ms	389460 KB	Output is correct
30	Correct	90 ms	389328 KB	Output is correct
31	Correct	92 ms	389384 KB	Output is correct
32	Correct	92 ms	389460 KB	Output is correct
33	Correct	91 ms	389668 KB	Output is correct
34	Correct	91 ms	389460 KB	Output is correct
35	Correct	90 ms	389416 KB	Output is correct
36	Correct	91 ms	389480 KB	Output is correct
37	Correct	93 ms	389528 KB	Output is correct
38	Correct	93 ms	389420 KB	Output is correct
39	Correct	92 ms	389344 KB	Output is correct
40	Correct	93 ms	389348 KB	Output is correct
41	Correct	91 ms	389552 KB	Output is correct
42	Incorrect	90 ms	389456 KB	Output isn't correct
43	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	389456 KB	Output is correct
2	Correct	165 ms	418424 KB	Output is correct
3	Correct	177 ms	418384 KB	Output is correct
4	Correct	154 ms	418232 KB	Output is correct
5	Correct	167 ms	418384 KB	Output is correct
6	Correct	156 ms	418252 KB	Output is correct
7	Correct	174 ms	418388 KB	Output is correct
8	Correct	91 ms	389460 KB	Output is correct
9	Correct	92 ms	389456 KB	Output is correct
10	Correct	95 ms	389404 KB	Output is correct
11	Correct	91 ms	389500 KB	Output is correct
12	Correct	92 ms	389532 KB	Output is correct
13	Correct	93 ms	389512 KB	Output is correct
14	Correct	89 ms	389336 KB	Output is correct
15	Correct	91 ms	389460 KB	Output is correct
16	Correct	90 ms	389460 KB	Output is correct
17	Correct	90 ms	389712 KB	Output is correct
18	Correct	92 ms	389432 KB	Output is correct
19	Correct	92 ms	389512 KB	Output is correct
20	Correct	340 ms	420880 KB	Output is correct
21	Correct	321 ms	420572 KB	Output is correct
22	Correct	321 ms	420584 KB	Output is correct
23	Correct	294 ms	421204 KB	Output is correct
24	Correct	294 ms	420692 KB	Output is correct
25	Correct	300 ms	420796 KB	Output is correct
26	Correct	376 ms	420800 KB	Output is correct
27	Correct	91 ms	389460 KB	Output is correct
28	Correct	96 ms	389708 KB	Output is correct
29	Correct	92 ms	389460 KB	Output is correct
30	Correct	90 ms	389328 KB	Output is correct
31	Correct	92 ms	389384 KB	Output is correct
32	Correct	92 ms	389460 KB	Output is correct
33	Correct	91 ms	389668 KB	Output is correct
34	Correct	91 ms	389460 KB	Output is correct
35	Correct	90 ms	389416 KB	Output is correct
36	Correct	91 ms	389480 KB	Output is correct
37	Correct	93 ms	389528 KB	Output is correct
38	Correct	93 ms	389420 KB	Output is correct
39	Correct	92 ms	389344 KB	Output is correct
40	Correct	93 ms	389348 KB	Output is correct
41	Correct	91 ms	389552 KB	Output is correct
42	Incorrect	90 ms	389456 KB	Output isn't correct
43	Halted	0 ms	0 KB	-

Subtask #6

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	389456 KB	Output is correct
2	Correct	165 ms	418424 KB	Output is correct
3	Correct	177 ms	418384 KB	Output is correct
4	Correct	154 ms	418232 KB	Output is correct
5	Correct	167 ms	418384 KB	Output is correct
6	Correct	156 ms	418252 KB	Output is correct
7	Correct	174 ms	418388 KB	Output is correct
8	Correct	91 ms	389460 KB	Output is correct
9	Correct	92 ms	389456 KB	Output is correct
10	Correct	95 ms	389404 KB	Output is correct
11	Correct	91 ms	389500 KB	Output is correct
12	Correct	92 ms	389532 KB	Output is correct
13	Correct	93 ms	389512 KB	Output is correct
14	Correct	89 ms	389336 KB	Output is correct
15	Correct	91 ms	389460 KB	Output is correct
16	Correct	90 ms	389460 KB	Output is correct
17	Correct	90 ms	389712 KB	Output is correct
18	Correct	92 ms	389432 KB	Output is correct
19	Correct	92 ms	389512 KB	Output is correct
20	Correct	340 ms	420880 KB	Output is correct
21	Correct	321 ms	420572 KB	Output is correct
22	Correct	321 ms	420584 KB	Output is correct
23	Correct	294 ms	421204 KB	Output is correct
24	Correct	294 ms	420692 KB	Output is correct
25	Correct	300 ms	420796 KB	Output is correct
26	Correct	376 ms	420800 KB	Output is correct
27	Correct	91 ms	389460 KB	Output is correct
28	Correct	96 ms	389708 KB	Output is correct
29	Correct	92 ms	389460 KB	Output is correct
30	Correct	90 ms	389328 KB	Output is correct
31	Correct	92 ms	389384 KB	Output is correct
32	Correct	92 ms	389460 KB	Output is correct
33	Correct	91 ms	389668 KB	Output is correct
34	Correct	91 ms	389460 KB	Output is correct
35	Correct	90 ms	389416 KB	Output is correct
36	Correct	91 ms	389480 KB	Output is correct
37	Correct	93 ms	389528 KB	Output is correct
38	Correct	93 ms	389420 KB	Output is correct
39	Correct	92 ms	389344 KB	Output is correct
40	Correct	93 ms	389348 KB	Output is correct
41	Correct	91 ms	389552 KB	Output is correct
42	Incorrect	90 ms	389456 KB	Output isn't correct
43	Halted	0 ms	0 KB	-

Subtask #7

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	389456 KB	Output is correct
2	Correct	93 ms	389460 KB	Output is correct
3	Correct	89 ms	389320 KB	Output is correct
4	Correct	92 ms	389448 KB	Output is correct
5	Correct	89 ms	389460 KB	Output is correct
6	Correct	92 ms	389460 KB	Output is correct
7	Correct	92 ms	389792 KB	Output is correct
8	Correct	93 ms	389460 KB	Output is correct
9	Correct	92 ms	389516 KB	Output is correct
10	Correct	92 ms	389456 KB	Output is correct
11	Correct	92 ms	389416 KB	Output is correct
12	Correct	96 ms	389456 KB	Output is correct
13	Correct	91 ms	389312 KB	Output is correct
14	Correct	95 ms	389456 KB	Output is correct
15	Correct	93 ms	389456 KB	Output is correct
16	Correct	92 ms	389460 KB	Output is correct
17	Correct	94 ms	389460 KB	Output is correct
18	Correct	93 ms	389396 KB	Output is correct
19	Correct	90 ms	389456 KB	Output is correct
20	Correct	95 ms	389528 KB	Output is correct
21	Correct	91 ms	389524 KB	Output is correct
22	Correct	89 ms	389488 KB	Output is correct
23	Correct	89 ms	389456 KB	Output is correct
24	Correct	93 ms	389684 KB	Output is correct
25	Correct	92 ms	389460 KB	Output is correct
26	Correct	93 ms	389504 KB	Output is correct
27	Correct	91 ms	389324 KB	Output is correct
28	Correct	90 ms	389460 KB	Output is correct
29	Correct	91 ms	389428 KB	Output is correct
30	Correct	90 ms	389456 KB	Output is correct
31	Correct	91 ms	389380 KB	Output is correct
32	Correct	94 ms	389460 KB	Output is correct
33	Correct	100 ms	389632 KB	Output is correct
34	Correct	93 ms	389460 KB	Output is correct
35	Correct	92 ms	389500 KB	Output is correct
36	Correct	93 ms	389400 KB	Output is correct
37	Incorrect	93 ms	389472 KB	Output isn't correct
38	Halted	0 ms	0 KB	-