Submission #860715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
860715	2023-10-14T02:40:00 Z	willychan	Council (JOI23_council)	C++14	0 / 100	401 ms	29416 KB

council

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
#define pii pair<int,int>
#define ff first
#define ss second
const int M = (1<<20)+5;
const int N = 300005;
pair<int,int> dis[M][2];
bool vote[N][20];
int ans[M];
int rs = 0;	
int n,m;
int care[20];
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<(1<<m);i++){
		for(int b=0;b<2;b++) dis[i][b] = {1e9,-1};
	}
	queue<pii > q;
	for(int i=0;i<n;i++){
		int s=0;
		for(int j=0;j<m;j++){
			cin>>vote[i][j];
			if(vote[i][j]) s+=(1<<j);
		}
		if(dis[s][0].ff!=1e9){
			dis[s][1] = {0,i};
			q.push({s,1});
		}else{
			dis[s][0] = {0,i};
			q.push({s,0});
		}
	}
	int base=0;
	for(int i=0;i<m;i++){
		int cnt = 0;	
		for(int j=0;j<n;j++) if(vote[j][i]) cnt++;
		care[i]=0;
		if(cnt==(n/2)){
			care[i]=1;
		}else if(cnt==(n/2)+1){	
			care[i]=2;
		}else if(cnt>=(n/2)+2) base++;
	}
	while(q.size()){
		pii cur = q.front();
		q.pop();
		for(int j=0;j<m;j++){
			int c= cur.ff^(1<<j);
			if(dis[c][0].ff>dis[cur.ff][cur.ss].ff+1){
				dis[c][0] = {dis[cur.ff][cur.ss].ff+1, dis[cur.ff][cur.ss].ss};
				q.push({c,0});
			}else if(dis[c][1].ff>dis[cur.ff][cur.ss].ff+1 && dis[c][0].ss!=dis[cur.ff][cur.ss].ss){
				dis[c][1] = {dis[cur.ff][cur.ss].ff+1,dis[cur.ff][cur.ss].ss};
				q.push({c,0});
			}
		}
		//for(int i=0;i<(1<<m);i++) cout<<dis[i][0].ff<<","<<dis[i][0].ss<<" "<<dis[i][1].ff<<","<<dis[i][1].ss<<"|\n"[(i%4==3)];
		//cout<<"\n\n\n";
	}

			

	for(int j=0;j<m;j++){
		for(int i=0;i<(1<<m);i++){
			if((i>>j)&1){
				int c = i^(1<<j);
				if(dis[i][1].ff<dis[c][0].ff) continue;					
				if(dis[i][0].ss!=dis[c][0].ss){
					if(dis[i][0].ff<dis[c][0].ff) dis[i][1] = dis[c][0];
					else{
						dis[i][1] = dis[i][0];
						dis[i][0] = dis[c][0];
					}
				}else{
					dis[i][0] = min(dis[i][0],dis[c][0]);
					dis[i][1] = min(dis[i][1],dis[c][1]);
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		int re = base;
		int s=0;
		int posi=0;
		for(int j=0;j<m;j++){
			if(vote[i][j]!=care[j]-1) s+=(1<<j);
			else posi++;
			if(care[j]==2 && vote[i][j]==0) re++;
		}
		if(dis[s][0].ss==i) posi-=dis[s][1].ff;
		else posi-=dis[s][0].ff;
		cout<<re+posi<<"\n";
	}
	return 0;
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	2 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	288 ms	25428 KB	Output is correct
6	Correct	182 ms	22100 KB	Output is correct
7	Correct	313 ms	24144 KB	Output is correct
8	Correct	374 ms	26288 KB	Output is correct
9	Correct	398 ms	29292 KB	Output is correct
10	Correct	315 ms	24900 KB	Output is correct
11	Correct	377 ms	26680 KB	Output is correct
12	Correct	401 ms	29416 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Incorrect	1 ms	4556 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	2 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	288 ms	25428 KB	Output is correct
6	Correct	182 ms	22100 KB	Output is correct
7	Correct	313 ms	24144 KB	Output is correct
8	Correct	374 ms	26288 KB	Output is correct
9	Correct	398 ms	29292 KB	Output is correct
10	Correct	315 ms	24900 KB	Output is correct
11	Correct	377 ms	26680 KB	Output is correct
12	Correct	401 ms	29416 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Incorrect	1 ms	4556 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	51 ms	11604 KB	Output is correct
3	Correct	57 ms	13060 KB	Output is correct
4	Correct	35 ms	12116 KB	Output is correct
5	Correct	51 ms	12760 KB	Output is correct
6	Correct	40 ms	12116 KB	Output is correct
7	Correct	54 ms	12848 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Incorrect	1 ms	4444 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	51 ms	11604 KB	Output is correct
3	Correct	57 ms	13060 KB	Output is correct
4	Correct	35 ms	12116 KB	Output is correct
5	Correct	51 ms	12760 KB	Output is correct
6	Correct	40 ms	12116 KB	Output is correct
7	Correct	54 ms	12848 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Incorrect	1 ms	4444 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	51 ms	11604 KB	Output is correct
3	Correct	57 ms	13060 KB	Output is correct
4	Correct	35 ms	12116 KB	Output is correct
5	Correct	51 ms	12760 KB	Output is correct
6	Correct	40 ms	12116 KB	Output is correct
7	Correct	54 ms	12848 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Incorrect	1 ms	4444 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	51 ms	11604 KB	Output is correct
3	Correct	57 ms	13060 KB	Output is correct
4	Correct	35 ms	12116 KB	Output is correct
5	Correct	51 ms	12760 KB	Output is correct
6	Correct	40 ms	12116 KB	Output is correct
7	Correct	54 ms	12848 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Incorrect	1 ms	4444 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	2 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	288 ms	25428 KB	Output is correct
6	Correct	182 ms	22100 KB	Output is correct
7	Correct	313 ms	24144 KB	Output is correct
8	Correct	374 ms	26288 KB	Output is correct
9	Correct	398 ms	29292 KB	Output is correct
10	Correct	315 ms	24900 KB	Output is correct
11	Correct	377 ms	26680 KB	Output is correct
12	Correct	401 ms	29416 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Incorrect	1 ms	4556 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Submission #860715

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 8.0

Subtask #3 0 / 6.0

Subtask #4 0 / 19.0

Subtask #5 0 / 15.0

Subtask #6 0 / 22.0

Subtask #7 0 / 22.0

Subtask #1
0 / 8.0

Subtask #2
0 / 8.0

Subtask #3
0 / 6.0

Subtask #4
0 / 19.0

Subtask #5
0 / 15.0

Subtask #6
0 / 22.0

Subtask #7
0 / 22.0