제출 #810463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810463		azberjibiou	Council (JOI23_council)	C++17	100 / 100	1760 ms	53924 KiB

council

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppi pair<pii, pii>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=300020;
const int mxM=25;
const int mxK=1200000;
const int MOD=1e9+7;
const ll INF=1e18;
typedef struct pnt{
    int dis, src, pos;
    pnt() : dis(), src(), pos() {}
    pnt(int dis, int src, int pos) : dis(dis), src(src), pos(pos) {}
}pnt;
int N, M;
int A[mxN];
int cnt[mxM], imp[mxN];
int one[mxN];
void input()
{
    cin >> N >> M;
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<M;j++)
        {
            int a;  cin >> a;
            A[i]+=a*(1<<j);
        }
    }
}
void make_cnt()
{
    for(int i=0;i<M;i++)
    {
        for(int j=1;j<=N;j++)   cnt[i]+=((A[j]>>i)&1);

        if(cnt[i]>=N/2+2)   for(int j=1;j<=N;j++)   one[j]++;
        if(cnt[i]<N/2)  continue;
        if(cnt[i]==N/2)
        {
            for(int j=1;j<=N;j++)   if((A[j]&(1<<i))==0)    imp[j]+=(1<<i);
        }
        if(cnt[i]==N/2+1)
        {
            for(int j=1;j<=N;j++)
            {
                if(A[j]&(1<<i)) imp[j]+=(1<<i);
                else    one[j]++;
            }
        }
    }
    for(int i=1;i<=N;i++)   imp[i]^=((1<<M)-1);
}
pair<pii, pii> D[mxK];
void bfs()
{
    queue <pnt> que;
    for(int i=1;i<=N;i++)
    {
        bool ok=false;
        if(D[A[i]].fi.se==0)    D[A[i]].fi=pii(0, i), ok=true;
        else if(D[A[i]].se.se==0)   D[A[i]].se=pii(0, i), ok=true;
        if(ok)  que.emplace(0, i, A[i]);
    }
    while(que.size())
    {
        auto [dis, src, now]=que.front();
        que.pop();
        for(int i=0;i<M;i++)
        {
            int nxt=(now^(1<<i));
            if(D[nxt].fi.se==0)
            {
                D[nxt].fi=pii(dis+1, src);
                que.emplace(dis+1, src, nxt);
            }
            else if(D[nxt].se.se==0 && D[nxt].fi.se!=src)
            {
                D[nxt].se=pii(dis+1, src);
                que.emplace(dis+1, src, nxt);
            }
        }
    }
}
pair<pii, pii> mrg(pair<pii, pii> a, pair<pii, pii> b)
{
    pair<pii, pii> res;
    res.fi=pii(), res.se=pii();
    vector <pii> t;
    if(a.fi.se!=0)  t.push_back(a.fi);
    if(a.se.se!=0)  t.push_back(a.se);
    if(b.fi.se!=0)  t.push_back(b.fi);
    if(b.se.se!=0)  t.push_back(b.se);
    sort(all(t));
    for(pii a : t)
    {
        if(res.fi.se==0)    res.fi=a;
        else if(res.se.se==0 && res.fi.se!=a.se)    res.se=a;
    }
    return res;
}
void imos_hanbyeol()
{
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<(1<<M);j++)
        {
            if(j&(1<<i))    D[j]=mrg(D[j], D[j-(1<<i)]);
        }
    }
}
int main()
{
    gibon
    input();
    make_cnt();
    bfs();
    imos_hanbyeol();
    for(int i=1;i<=N;i++)
    {
        if(D[imp[i]].fi.se==i)  cout << one[i]+M-__builtin_popcount(imp[i])-D[imp[i]].se.fi << '\n';
        else    cout << one[i]+M-__builtin_popcount(imp[i])-D[imp[i]].fi.fi << '\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