Submit Info #64622

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 1371 ms 4.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.42 MiB
hand_minus_00 AC 1371 ms 4.32 MiB
hand_plus_00 AC 405 ms 4.36 MiB
max_random_00 AC 404 ms 4.34 MiB
max_random_01 AC 405 ms 4.37 MiB
max_random_02 AC 409 ms 4.39 MiB
max_random_03 AC 406 ms 4.32 MiB
max_random_04 AC 404 ms 4.29 MiB
random_00 AC 29 ms 1.07 MiB
random_01 AC 37 ms 1.10 MiB
random_02 AC 6 ms 0.61 MiB
random_03 AC 35 ms 1.07 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define all(c) ((c).begin()), ((c).end()) #define sz(x) ((int)(x).size()) #ifdef LOCAL #include <print.h> #else #define trace(...) // remove in interactive #define endl '\n' #endif const ll INF = 1e18; #define int long long struct Data{ vector<pair<ll, int>> seq; Data(){} void insert(int i){ seq.push_back({i, 0}); } void add(ll v){ seq.push_back({v, 1}); } void update(vector<ll> & X){ reverse(all(seq)); ll sum = 0; for(auto it: seq){ if(it.second == 0){ X[it.first] += sum; } else{ sum += it.first; } } } }; // 0-indexed struct segtree{ int n; vector<int> t; vector<ll> arr; inline int combine(int a, int b){ if(a == -1) return b; if(b == -1) return a; return arr[a] < arr[b] ? a : b; } segtree(vector<ll> val) : n(val.size()), arr(val.size(), INF){ t.resize(2 * n, -1); arr = val; for(int i = 0; i < n; i++) t[n + i] = i; for(int i = n - 1; i > 0; --i) t[i] = combine(t[i<<1], t[i<<1|1]); } void erase(int p){ p -= n; for (t[p += n] = -1; p >>= 1; ) t[p] = combine(t[p<<1], t[p<<1|1]); } void modify(int p, ll value) { // modify a[p] = value p -= n; arr[p] = value; for (p += n; p >>= 1; ) t[p] = combine(t[p<<1], t[p<<1|1]); } }; struct graph{ vector<vector<ll>> W; vector<vector<int>> adj; vector<int> mate; vector<ll> A; int n; graph(int n): n(n), adj(n), mate(2 * n, -1), A(2 * n), W(n, vector<ll>(n)){ for(int i = 0; i < n; i++) A[i] = INF; } void add_edge(int x, int y, ll w){ adj[x].push_back(y); W[x][y] = max(W[x][y], w); } bool increment(){ vector<int> prev(2 * n, -1); Data visited_left, visited_right; segtree Delta(vector<ll>(n, INF)); segtree unvisited_right(vector<ll> (A.begin() + n, A.begin() + 2 * n)); vector<int> partnerLeft(2 * n, -1); ll sum = 0; vector<ll> delta(2 * n, INF); vector<bool> vis(n); int smallest_vis = -1; ll smallest_val = INF; bool ret = false; function<void(int)> backtrack = [&](int y){ ret = true; while(y != -1){ int s = prev[y]; int _y = mate[s]; mate[s] = y; mate[y] = s; y = _y; } }; function<bool(int)> augment = [&](int s){ if(A[s] < smallest_val){ smallest_vis = s; smallest_val = A[s]; } visited_left.insert(s); vis[s] = true; for(int x: adj[s]){ int y = x + n; int v = mate[y]; if(v == s || (v != -1 && vis[v])) continue; if(A[s] + A[y] == W[s][x]){ prev[y] = s; unvisited_right.erase(y); Delta.erase(y); visited_right.insert(y); if(v == -1 || augment(v)){ if(v==-1) backtrack(y); return true; } } else if(A[s] + A[y] - W[s][x] < delta[y] - sum){ Delta.modify(y, delta[y] = A[s] + A[y] - W[s][x] + sum); partnerLeft[y] = s; } } while(true){ int y = unvisited_right.t[1]; if(y == -1) break; y += n; int v = mate[y]; if(A[s] + A[y] == 0){ prev[y] = s; unvisited_right.erase(y); Delta.erase(y); visited_right.insert(y); if(v == -1 || augment(v)){ if(v==-1) backtrack(y); return true; } } break; } return false; }; function<void(ll)> add = [&](ll d){ visited_left.add(-d); visited_right.add(d); smallest_val -= d; sum += d; }; queue<int> Q; for(int i = 0; i < n; i++) if(mate[i] == -1) Q.push(i); while(!ret && !Q.empty()){ while(!Q.empty()){ int u = Q.front(); Q.pop(); if(vis[u]) continue; if(augment(u)) break; } if(ret) break; ll wt = Delta.arr[Delta.t[1]] - sum; ll wt2 = smallest_val + unvisited_right.arr[unvisited_right.t[1]]; ll w = min(wt, wt2); add(w); while(true){ int y = Delta.t[1]; if(y==-1) break; y += n; if(delta[y] == sum){ Delta.erase(y); unvisited_right.erase(y); prev[y] = partnerLeft[y]; if(mate[y] == -1){ backtrack(y); ret = true; break; } visited_right.insert(y); Q.push(mate[y]); } else{ break; } } if(ret) break; while(true){ int y = unvisited_right.t[1]; if(y == -1) break; y += n; if(A[y] + smallest_val == 0){ unvisited_right.erase(y); Delta.erase(y); prev[y] = smallest_vis; if(mate[y] == -1){ backtrack(y); ret = true; break; } visited_right.insert(y); Q.push(mate[y]); } else{ break; } } } visited_left.update(A); visited_right.update(A); return ret; } ll max_matching(){ while(increment()){} ll sum = 0; for(int i = 0; i < n; i++) sum += W[i][mate[i] - n]; return sum; } }; signed main(){ int n; cin >> n; graph G(n); const ll offset = 3e9; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++){ int x; cin >> x; G.add_edge(i, j, offset - x); } } cout << offset * n - G.max_matching() << endl; for(int i = 0; i < n; i++) cout << G.mate[i] - n <<" "; cout << endl; }