제출 #1338506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338506		moondarkside	Council (JOI23_council)	C++20	100 / 100	1417 ms	521964 KiB

council

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


std::vector<int>A;
std::vector<pair<pair<int,int>,int>> DIST;

void DISKTRA(int m,vector<int> & Values){
    
    stack<pair<int,pair<int,int>>> Q;
    stack<pair<int,pair<int,int>>> S;
    stack<pair<int,pair<int,int>>> P;
    
    for(int i=0;i<Values.size();i++){
        Q.push({0,{Values[i],i}});
    }
    
    while(!Q.empty()){
    while(!Q.empty()){
        int D=-Q.top().first;
        int n=Q.top().second.first;
        int ElP=Q.top().second.second;
        bool run=false;
        if(DIST[n].first.first==-1){
            DIST[n].first={D,ElP};
            run=true;
        }
        else if(DIST[n].second==-1 && DIST[n].first.second!=ElP){
            DIST[n].second=D;
            run=true;
        }
        Q.pop();
        if(run){
            
            for(int i=0;i<m;i++){
                
                if((n & (1<<i)) == 0 ){
                    Q.push({-D,{n ^ (1<<i),ElP}});
                }
                else{
                    S.push({-(D+1),{n ^ (1<<i),ElP}});
                }
                
                
                
            }
            
            
        }
        
        
    }
    Q=S;
    S=P;
    }
    
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> AM(m);
    A=vector<int>(n);
    for(int i=0;i<n;i++){
        int a=0;
        for(int j=0;j<m;j++){
            int c;
            cin>>c;
            a=a| (1<<j)*c;
            AM[j]+=c;
        }
        A[i]=a;
        
        
    }
    
    
    DIST=vector<pair<pair<int,int>,int>>(1<<m,{{-1,-1},-1});
    
    int SC=0;
    int C=0;
    int am=0;
    for(int i=0;i<m;i++){
        if(AM[i]==n/2){
            C=C|(1<<i);
            am++;
        }
        if(AM[i]-1==n/2){
            SC=SC|(1<<i);
            am++;
            
        }
        if(AM[i]-1>n/2){
            am++;
        }
    }
    int MIX=SC | C;
    for(int i=0;i<n;i++){
        
        A[i]=A[i]&MIX;
        
        
    }
    DISKTRA(m,A);

    for(int i=0;i<n;i++){
        
        int element=A[i]^SC;
        int amp=am;
        if(DIST[element].first.second==i){
            amp-=DIST[element].second;
        }
        else{
            amp-=DIST[element].first.first;
        }
        
        for(int j=0;j<m;j++){
            
            if((A[i] & C & (1<<j))!=0){
                amp--;
            }
            
        }
        cout<<amp<<"\n";
        
        
        
    }
    
}

• 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