Submission #1029910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029910		adaawf	Council (JOI23_council)	C++17	70 / 100	4019 ms	805560 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], d[300005];
vector<vector<int>> f, g;
vector<vector<deque<pair<int, int>>>> dd;
priority_queue<pair<long long int, pair<int, int>>> q;
int ch(int x) {
    return __builtin_popcount(x);
}
void trans(int x, int y, int z, int t, int w, int l) {
    int h = dd[z][t].size();
    for (auto w : dd[x][y]) {
        dd[z][t].push_back({w.first - l, w.second});
    }
    sort(dd[z][t].begin(), dd[z][t].end());
    pair<int, int> res = {-1, -1};
    while (dd[z][t].size() >= 2) {
        auto h = dd[z][t].front();
        if (h.second != (dd[z][t].back()).second) res = h;
        dd[z][t].pop_front();
    }
    if (res.first != -1) dd[z][t].push_back(res);
    if (dd[z][t].size() != 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;
        d[i] = k;
    }
    g = vector<vector<int>>((1 << z), vector<int>(1 << zz, 0));
    dd = vector<vector<deque<pair<int, int>>>>((1 << z), vector<deque<pair<int, int>>>(1 << zz));
    for (int i = 1; i <= n; i++) {
        dd[x[i]][y[i]].push_back({ch(x[i]) + ch(y[i]), i});
        if (dd[x[i]][y[i]].size() > 2) dd[x[i]][y[i]].pop_back();
        //cout << i << " " << x[i] << " " << y[i] << " " << d[i] << '\n';
        if (dd[x[i]][y[i]].size() == 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 (dd[u][v].empty() || g[u][v] == 1) continue;
        g[u][v] = 1;
        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);
            }
        }
    }
    f = vector<vector<int>>((1 << z), vector<int>(1 << zz, -1e9));
    for (int i = 0; i < (1 << z); i++) {
        for (int j = 0; j < (1 << zz); j++) {
            if (g[i][j] == 1) {
                f[i][j] = ch(i) + ch(j);
                /*for (auto w : dd[i][j]) cout << w.first << "|" << w.second << " ";
                cout << '\n';*/
                q.push({f[i][j], {i, j}});
            }
        }
    }
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        int x = p.first, u = p.second.first, v = p.second.second;
        /*cout << 12131 << " " << u << " " << v << '\n';
        for (auto w : dd[u][v]) cout << w.first << "|" << w.second << " ";
        cout << '\n';*/
        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;
        for (auto w : dd[x[i]][d[i]]) {
            if (w.second != i) {
                h = max(h, w.first);
                //cout << i << " " << x[i] << " " << d[i] << " " << w.first << " " << w.second << '\n';
            }
        }
        h += ch(y[i]);
        cout << m - (z + zz - h) - l << '\n';
    }
}

Compilation message (stderr)

council.cpp: In function 'void trans(int, int, int, int, int, int)':
council.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     if (dd[z][t].size() != h) q.push({w, {z, t}});
      |         ~~~~~~~~~~~~~~~~^~~~

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