結果

問題 No.1900 Don't be Powers of 2
コンテスト
ユーザー 🍮かんプリン
提出日時 2022-04-11 02:57:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 331 ms / 2,000 ms
コード長 6,421 bytes
コンパイル時間 2,632 ms
コンパイル使用メモリ 204,436 KB
実行使用メモリ 68,352 KB
最終ジャッジ日時 2024-12-14 19:15:29
合計ジャッジ時間 5,795 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2022.04.11 02:57:41
**/

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


struct Dinic {
private:
    struct edge {
        int to;
        ll cap;
        int rev;
        bool isrev;
        int idx;
    };

    vector< vector< edge > > graph;
    vector< int > min_cost, iter;

    bool bfs(int s, int t) {
        min_cost.assign(graph.size(), -1);
        queue< int > que;
        min_cost[s] = 0;
        que.push(s);
        while (!que.empty() && min_cost[t] == -1) {
            int p = que.front();
            que.pop();
            for (auto &e : graph[p]) {
                if (e.cap == 0 || min_cost[e.to] != -1) continue;
                min_cost[e.to] = min_cost[p] + 1;
                que.push(e.to);
            }
        }
        return min_cost[t] != -1;
    }

    ll dfs(const int s, int v, ll flow) {
        if (v == s) return flow;
        ll res = 0;
        int min_cost_v = min_cost[v];
        for (int &i = iter[v]; i < (int)graph[v].size(); i++) {
            edge &e = graph[v][i];
            if (graph[e.to][e.rev].cap == 0 || min_cost_v <= min_cost[e.to]) continue;
            ll d = dfs(s, e.to, min(flow-res, graph[e.to][e.rev].cap));
            if (d <= 0) continue;
            e.cap += d;
            graph[e.to][e.rev].cap -= d;
            res += d;
            if (res == flow) return res;
        }
        min_cost[v] = (int)graph.size();
        return res;
    }
public:

    Dinic() {}
    Dinic(int V) : graph(V) {}

    void add_edge(int from, int to, ll cap, int idx = -1) {
        graph[from].push_back({to, cap, (int)graph[to].size(), false, idx});
        graph[to].push_back({from, 0, (int)graph[from].size() - 1, true, idx});
    }

    ll max_flow(int s, int t, ll flow_limit = 1e18 + 6) {
        ll flow = 0;
        while (bfs(s, t)) {
            if (min_cost[t] == -1) break;
            iter.assign(graph.size(), 0);
            ll f = dfs(s, t, flow_limit-flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    vector<int> min_cnt(int s,int t) {
        vector<bool> visited(graph.size());
        vector<int> ret;
        stack<int> sta;
        visited[s] = true;
        sta.push(s); ret.push_back(s);
        while(!sta.empty()) {
            int v = sta.top(); sta.pop();
            for (auto &e : graph[v]) {
                if (visited[e.to] || e.cap == 0) continue;
                visited[e.to] = true;
                sta.push(e.to);
                ret.push_back(e.to);
            }
        }
        return ret;
    }

    void output() {
        for (int i = 0; i < graph.size(); i++) {
            for (auto &e : graph[i]) {
                if (e.isrev) continue;
                auto &rev_e = graph[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};

struct ProjectSelectionProblem {
    const long long INF = 1e18+1;
    int n; 
    vector<int> k; 
    vector<int> s; 
    vector<vector<long long>> cost;
    Dinic G;
    long long ans;
    
    ProjectSelectionProblem(vector<int> k) : k(k) {
        n = k.size();
        s = vector<int>(n+1);
        s[0] = 0;
        for (int i = 0; i < n; i++) {
            assert(k[i] >= 2);
            s[i+1] = s[i]+k[i]-1;
        }
        cost = vector<vector<long long>>(n);
        for (int i = 0; i < n; i++) cost[i] = vector<long long>(k[i],0);
        G = Dinic(s[n]+2);
        ans = 0;
    }

    void add_cost_1(int a,vector<long long> x) {
        assert(0 <= a && a < n);
        assert(k[a] == (int)x.size());
        for (int i = 0; i < k[a]; i++) {
            cost[a][i] += x[i];
        }
    }

    void add_cost_2(int a,int b,vector<vector<long long>> x) {
        assert(0 <= a && a < n && 0 <= b && b < n);
        assert((int)x.size() == k[a]);
        for (int i = 0; i < k[a]; i++) {
            assert((int)x[i].size() == k[b]);
            cost[a][i] += x[i][0];
            for (int j = k[b]-1; j >= 0; j--) x[i][j] -= x[i][0];
        }
        for (int i = 1; i < k[b]; i++){
            cost[b][i] += x[k[a]-1][i];
            for (int j = 0; j < k[a]; j++) x[j][i] -= x[k[a]-1][i];
        }
        for (int i = 0; i < k[a]-1; i++){
            for (int j = 0; j < k[b]-1; j++){
                long long c = x[i+1][j]+x[i][j+1]-x[i][j]-x[i+1][j+1];
                assert(c >= 0);
                if (c == 0) continue;
                G.add_edge(s[b]+j, s[a]+i, c);
            }
        }
    }

    long long mincost() {
        for (int i = 0; i < n; i++){
            for (int j = 0; j < k[i]-2; j++) G.add_edge(s[i]+j+1, s[i]+j, INF);
            ans += cost[i][k[i]-1];
            for (int j = 0; j < k[i]-1; j++){
                if (cost[i][j] > cost[i][j+1]) {
                    G.add_edge(s[n], s[i]+j, cost[i][j]-cost[i][j+1]);
                }
                else {
                    G.add_edge(s[i]+j, s[n]+1, cost[i][j+1]-cost[i][j]);
                    ans -= cost[i][j+1]-cost[i][j];
                }
            }
        }
        return ans+G.max_flow(s[n], s[n]+1);
    }
};

int bitpopcount(ll n) {
    int res = 0;
    while (n) {
        if (n & 1) res++;
        n >>= 1;
    }
    return res;
}

int main() {
    int n;cin >> n;
    vector<int> a(n);
    map<int,int> mp;
    vector<vector<int>> v;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (mp.find(a[i]) != mp.end()) v[mp[a[i]]].push_back(i);
        else {
            mp[a[i]] = v.size();
            v.push_back(vector<int>());
            v.back().push_back(i);
        }
    }
    vector<int> k(n,2);
    ProjectSelectionProblem psp(k);
    for (int i = 0; i < n; i++) {
        vector<ll> x(2);
        int bpc = bitpopcount(a[i]);
        x[0] = (bpc%2==0?0:-1);
        x[1] = (bpc%2==0?-1:0);
        psp.add_cost_1(i,x);
        for (int j = 0; j < 30; j++) {
            if (a[i]&1<<j) continue;
            if (mp.find(a[i]|1<<j)==mp.end()) continue;
            vector<vector<ll>> x(2,vector<ll>(2));
            x[0][0] = x[1][1] = 0;
            x[0][1] = (bpc%2==0?0:1000000000);
            x[1][0] = (bpc%2==0?1000000000:0);
            for (int t : v[mp[a[i]|1<<j]]) {
                psp.add_cost_2(i,t,x);
            }
        }
    }
    cout << -psp.mincost() << endl;
    return 0;
}
0