Submission #1029933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029933		adaawf	Council (JOI23_council)	C++17	100 / 100	2041 ms	152980 KiB

council

#include <bits/stdc++.h>
using namespace std;
bool a[300005][21];
int c[21], da[21], db[21], z = 0, zz = 0;
int x[300005], y[300005];
vector<vector<int>> g;
#define pii pair<int, int>
vector<vector<pair<pii, pii>>> dd;
priority_queue<pair<long long int, pii>> q;
int ch(int x) {
    return __builtin_popcount(x);
}
vector<pair<int, int>> vv;
void trans(int x, int y, int z, int t, int w, int l) {
    vv.clear();
    int h = 2;
    if (dd[z][t].first.first == -1) h = 0;
    else if (dd[z][t].second.first == -1) h = 1;
    vv.push_back({dd[x][y].first.first - l, dd[x][y].first.second});
    vv.push_back({dd[x][y].second.first - l, dd[x][y].second.second});
    vv.push_back(dd[z][t].first);
    vv.push_back(dd[z][t].second);
    pii k = {-1, -1}, res = k;
    for (auto w : vv) {
        if (w.first > k.first) k = w;
    }
    for (auto w : vv) {
        if (w.first > res.first && w.second != k.second) {
            res = w;
        }
    }
    dd[z][t].second = {-1, -1};
    dd[z][t].first = k;
    int g = 1;
    if (res.first != -1) dd[z][t].second = res, g = 2;
    if (g != h) q.push({w, {z, t}});
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, l = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            c[j] += a[i][j];
        }
    }
    for (int j = 0; j < m; j++) {
        if (c[j] == n / 2) {
            da[j] = ++z;
        }
        else if (c[j] == (n / 2) + 1) {
            db[j] = ++zz;
        }
        else if (c[j] < n / 2) l++;
    }
    for (int i = 1; i <= n; i++) {
        int h = 0, k = 0;
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 1) {
                if (da[j] != 0) {
                    h += (1 << (da[j] - 1));
                }
                else if (db[j] != 0) {
                    k += (1 << (db[j] - 1));
                }
            }
        }
        x[i] = (1 << z) - h - 1;
        y[i] = (1 << zz) - k - 1;
    }
    g = vector<vector<int>>((1 << z), vector<int>(1 << zz, 0));
    dd = vector<vector<pair<pii, pii>>>((1 << z), vector<pair<pii, pii>>(1 << zz, {{-1, -1}, {-1, -1}}));
    for (int i = 1; i <= n; i++) {
        int flag = 0;
        if (dd[x[i]][y[i]].first.first == -1) {
            dd[x[i]][y[i]].first = {ch(x[i]) + ch(y[i]), i};
            flag = 1;
        }
        else dd[x[i]][y[i]].second = {ch(x[i]) + ch(y[i]), i};
        if (flag == 1) q.push({ch(x[i]) + ch(y[i]), {x[i], y[i]}});
    }
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        int x = p.first, u = p.second.first, v = p.second.second;
        if (g[u][v] == 1) continue;
        g[u][v] = 1;
        //cout << u << " " << v << " " << dd[u][v].first.first << " " << dd[u][v].first.second << " " << dd[u][v].second.first << " " << dd[u][v].second.second << '\n';
        for (int i = 0; i < z; i++) {
            if (u & (1 << i)) {
                trans(u, v, u - (1 << i), v, x - 1, 1);
            }
        }
        for (int i = 0; i < zz; i++) {
            if (v & (1 << i)) {
                trans(u, v, u, v - (1 << i), x - 1, 1);
            }
        }
    }
    for (int i = 0; i < (1 << z); i++) {
        for (int j = 0; j < (1 << zz); j++) {
            if (g[i][j] == 1) {
                q.push({ch(i) + ch(j), {i, j}});
            }
        }
    }
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        int x = p.first, u = p.second.first, v = p.second.second;
        for (int i = 0; i < z; i++) {
            if (!(u & (1 << i))) {
                trans(u, v, u + (1 << i), v, x, 0);
            }
        }
        for (int i = 0; i < zz; i++) {
            if (!(v & (1 << i))) {
                trans(u, v, u, v + (1 << i), x, 0);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int h = 0;
        vector<pair<int, int>> v;
        v.push_back(dd[x[i]][(1 << zz) - y[i] - 1].first);
        v.push_back(dd[x[i]][(1 << zz) - y[i] - 1].second);
        for (auto w : v) {
            if (w.second != i) {
                h = max(h, w.first);
                //cout << i << " " << x[i] << " " << (1 << zz) - y[i] - 1 << " " << w.first << " " << w.second << '\n';
            }
        }
        h += ch(y[i]);
        cout << m - (z + zz - h) - l << '\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