Submission #3665018

---

Source Code Expand

#include <cassert>
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}

template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

vector<int> solve(const vector<int>& c) {
  int n = c.size();
  vector<int> res(n + 1, -1);
  {
    vector<vector<int>> dp1(n + 1, vector<int>(2, -1));
    vector<vector<int>> dp2(n + 1, vector<int>(2, -1));
    dp1[0][0] = 0;
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= n; ++j) dp2[j][0] = dp2[j][1] = -1;
      for (int j = 0; j <= i; ++j) {
        if (dp1[j][0] != -1) {
          chmax(dp2[j + 1][0], dp1[j][0] + c[i]);
          chmax(dp2[j + 1][1], dp1[j][0] + 2 * c[i]);
        }
        if (dp1[j][1] != -1) {
          chmax(dp2[j][0], dp1[j][1]);
          chmax(dp2[j + 1][1], dp1[j][1] + c[i]);
        }
      }
      swap(dp1, dp2);
    }
    /*
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j < 2; ++j) {
        cerr << dp1[i][j] << " ";
      }
      cerr << endl;
    }
    */
    for (int i = 0; i <= n; ++i) {
      if (dp1[i][0] != -1) chmax(res[i + 1], dp1[i][0] + c[0]);
      if (dp1[i][1] != -1) chmax(res[i], dp1[i][1]);
    }
  }
  {
    vector<vector<int>> dp1(n + 1, vector<int>(2, -1));
    vector<vector<int>> dp2(n + 1, vector<int>(2, -1));
    dp1[1][1] = c[0];
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= n; ++j) dp2[j][0] = dp2[j][1] = -1;
      for (int j = 0; j <= i; ++j) {
        if (dp1[j][0] != -1) {
          chmax(dp2[j + 1][0], dp1[j][0] + c[i]);
          chmax(dp2[j + 1][1], dp1[j][0] + 2 * c[i]);
        }
        if (dp1[j][1] != -1) {
          chmax(dp2[j][0], dp1[j][1]);
          chmax(dp2[j + 1][1], dp1[j][1] + c[i]);
        }
      }
      swap(dp1, dp2);
    }
    for (int i = 0; i <= n; ++i) {
      if (dp1[i][0] != -1) chmax(res[i], dp1[i][0] + c[0]);
      if (dp1[i][1] != -1) chmax(res[i], dp1[i][1]);
    }
  }
  return res;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  cin >> a >> b;
  vector<vector<int>> g(n);
  for (int i = 0; i < n; ++i) {
    g[a[i] - 1].emplace_back(b[i] - 1);
    g[b[i] - 1].emplace_back(a[i] - 1);
  }
  vector<vector<int>> c;
  vector<bool> used(n);
  for (int i = 0; i < n; ++i) {
    if (used[i]) continue;
    int v = i, p = -1;
    vector<int> circle;
    do {
      used[v] = true;
      circle.emplace_back(v + 1);
      auto u = g[v][0];
      if (u == p) u = g[v][1];
      p = v;
      v = u;
    } while (v != i);
    c.emplace_back(circle);
  }
  vector<int> dp(n + 1, -1);
  dp[0] = 0;
  for (int i = 0; i < int(c.size()); ++i) {
    auto v = solve(c[i]);
    //cerr << v;
    vector<int> dp2(n + 1, -1);
    for (int j = 0; j <= n; ++j) {
      if (dp[j] == -1) continue;
      for (int x = c[i].size() / 2; x < int(v.size()) && j + x <= n; ++x) {
        if (v[x] == -1) continue;
        chmax(dp2[j + x], dp[j] + v[x]);
      }
    }
    dp = dp2;
  }
  int res = 0;
  for (int i = k; i <= n; ++i) chmax(res, dp[i]);
  cout << res << endl;
}

Submission Info

Judge Result