oj.uz

Submission #914477

# Submission time Handle Problem Language Result Execution time Memory
914477 2024-01-22T08:46:47 Z vjudge1 Council (JOI23_council) C++17
6 / 100
 376 ms 421204 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -