Submission #789214

#	Time	Username	Problem	Language	Result	Execution time	Memory
789214		esomer	Council (JOI23_council)	C++17	100 / 100	1043 ms	39344 KiB

council

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long ll;

struct Node{
	int mx, mx2, f, s;
	
	void upd(int val, int i){
		if(i != f && i != s){
			if(val > mx){
				s = f;
				mx2 = mx;
				f = i;
				mx = val;
			}else if(val > mx2){
				s = i;
				mx2 = val;
			}
		}else if(i == f && i != s){
			//The second maximum remains the same, I can only change the first maximum.
			if(val > mx){
				f = i;
				mx = val;
			}
		}else if(i != f && i == s){
			//I can either change the first maximum and set it to second maximum, or change directly the second maximum, so proceed as normal.
			if(val > mx){
				s = f;
				mx2 = mx;
				f = i;
				mx = val;
			}else if(val > mx2){
				s = i;
				mx2 = val;
			}
		}
	}
};

int n, m; 

void process(vector<Node>& mx, vector<int>& changed){
	vector<bool> vis((1 << m), 0);
	priority_queue<pair<int, int>> q;
	for(int i = 0; i < n; i++){
		int bits = 0;
		for(int j = 0; j < m; j++){
			if((changed[i] & (1 << j))) bits++;
		}
		q.push({bits, changed[i]}); //If it takes the greater first, I want to go "down" (i.e. to masks with less bits on).
		mx[changed[i]].upd(bits, i);
	}
	while(!q.empty()){
		int bits = q.top().first; int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int j = 0; j < m; j++){
			if((1 << j) & x){
				int nw = x - (1 << j);
				pair<int, int> init = {mx[nw].mx, mx[nw].mx2};
				mx[nw].upd(mx[x].mx - 1, mx[x].f); //Because in this Dijkstra I'm only visiting the masks that are fully contained by an element. So they will all be full, and I only
				mx[nw].upd(mx[x].mx2 - 1, mx[x].s); //substract the bit that I am substracting.
				pair<int, int> after = {mx[nw].mx, mx[nw].mx2};
				if(init != after) q.push({bits - 1, nw});
			}
		}
	}
	vis.assign((1 << m), 0);
	for(int i = 0; i < (1 << m); i++){
		int bits = 0;
		for(int j = 0; j < m; j++){
			if((1 << j) & i) bits++;
		}
		if(mx[i].mx != -1) q.push({-bits, i});
	}
	while(!q.empty()){
		int bits = -q.top().first; int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int j = 0; j < m; j++){
			if(!((1 << j) & x)){
				int nw = x + (1 << j);
				pair<int, int> init = {mx[nw].mx, mx[nw].mx2};
				mx[nw].upd(mx[x].mx, mx[x].f);
				mx[nw].upd(mx[x].mx2, mx[x].s);
				pair<int, int> after = {mx[nw].mx, mx[nw].mx2};
				if(init != after) q.push({-(bits + 1), nw});
			}
		}
	}
}

void solve(){
	cin >> n >> m;
	int obj = n / 2; 
	vector<int> a(n);
	vector<int> changed(n);
	vector<int> cnt(m, 0);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			int x; cin >> x;
			if(x == 1) {a[i] += (1 << j); cnt[j]++;}
			else changed[i] += (1 << j);
		}
	}
	vector<Node> mx((1 << m), {-1, -1, -1, -1});
	process(mx, changed);
	for(int i = 0; i < n; i++){
		int add = 0;
		int mask = 0; //Here I add the ones that are exactly obj, so I want the other to have 0 in it so I don't lose it.
		for(int j = 0; j < m; j++){
			int v = cnt[j];
			if((1 << j) & a[i]) v--;
			if(v > obj) add++;
			else if(v == obj) mask += (1 << j);
		}
		int ans;
		if(mx[mask].f == i) ans = add + max(0, mx[mask].mx2);
		else ans = add + max(0, mx[mask].mx);
		cout << ans << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	//~ int tt; cin >> tt;
	int tt = 1;
	for(int t = 1; t <= tt; t++){
		solve();
	}
}

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