Submission #789322

#	Time	Username	Problem	Language	Result	Execution time	Memory
789322		Johann	Council (JOI23_council)	C++14	100 / 100	2390 ms	236928 KiB

council

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; }
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M;
vvi A;
vi votes;
int vr; // votes required
vi trans, transR;

struct node
{
    bool state;
    node *par = nullptr;
    node *next[2] = {nullptr, nullptr};
    vpii result;
};
void addRes(node *n, pii res)
{
    for (int i = 0; i < 2; ++i)
        if (n->result[i] < res)
            swap(n->result[i], res);
}
struct Trie
{
    vector<vector<node *>> layers;
    node *root;
    void init()
    {
        layers.resize(M + 1);
        root = new node();
        root->result.assign(2, {-1, -1});
        layers[0].push_back(root);
    }
    void insert(int v, pii id)
    {
        insert(v, id, 0, root);
    }
    void insert(int v, pii id, int idx, node *n)
    {
        if (idx == M)
        {
            addRes(n, id);
            return;
        }
        int st = (v >> idx) & 1;
        if (n->next[st] == nullptr)
        {
            n->next[st] = new node();
            n->next[st]->par = n;
            n->next[st]->state = st;
            n->next[st]->result.assign(2, {-1, -1});
            layers[idx + 1].push_back(n->next[st]);
        }
        insert(v, id, idx + 1, n->next[st]);
    }
    node *query(int v) { return query(v, 0, root); }
    node *query(int v, int idx, node *n)
    {
        if (n == nullptr)
            return nullptr;
        if (idx == M)
            return n;
        int st = (v >> idx) & 1;
        return query(v, idx + 1, n->next[st]);
    }
};
Trie Tid; // Tid
Trie Tma; // matching
const pii add1 = {1, 0};

void cleanuplayer(int idx)
{
    for (node *n : Tma.layers[M - idx])
        n->result.assign(2, {-1, -1});
}
void dfs(node *nid, int idx)
{
    // idx := layer in tid
    // M - idx := corespoding layer in Tma
    if (idx == M)
    {
        nid->result = Tma.layers[M - idx][0]->result;
    }
    else
    {
        for (int i = 0; i < 2; ++i)
        {
            if (nid->next[i] == nullptr)
                continue;

            for (node *n : Tma.layers[M - idx])
            {
                for (pii p : n->result)
                {
                    if (p.first == -1)
                        continue;
                    if (votes[idx] - i - n->state >= vr)
                        addRes(n->par, p + add1);
                    else
                        addRes(n->par, p);
                }
            }
            dfs(nid->next[i], idx + 1);

            cleanuplayer(idx + 1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    vr = N / 2;

    A.assign(N, vi(M));
    votes.assign(M, 0);
    trans.assign(N, 0);
    transR.assign(N, 0);
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> A[i][j];
            votes[j] += A[i][j];
            trans[i] |= (A[i][j]) ? (1 << j) : 0;
            transR[i] |= (A[i][j]) ? (1 << (M - 1 - j)) : 0;
        }
    }

    Tid.init();
    Tma.init();
    for (int i = 0; i < N; ++i)
        Tid.insert(trans[i], {-1, -1}), Tma.insert(transR[i], {0, i});

    dfs(Tid.root, 0);

    for (int i = 0; i < N; ++i)
    {
        node *tmp = Tid.query(trans[i]);
        if (tmp->result[0].second != i)
            cout << tmp->result[0].first << "\n";
        else
            cout << tmp->result[1].first << "\n";
    }

    return 0;
}

• 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