test/aoj/2370.test.cpp

• View this file on GitHub
• Last update: 2021-07-23 12:56:32+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370

Depends on

• algorithm/partialsum.cpp
• graph/bipartitedecomposition.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../graph/bipartitedecomposition.cpp"
#include "../../algorithm/partialsum.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  BipartiteDecomposition G(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v);
  }
  auto res=G.build();
  if(res.empty()){
    cout<<-1<<endl;
    return 0;
  }

  int offset=0;
  vector<int> vs;
  for(auto[x,y]:res){
    offset+=min(x,y);
    vs.emplace_back(abs(x-y));
  }
  auto dp=partial_sum<100000>(vs);

  long long ans=0;
  for(int i=0;i<=n;i++){
    if(!dp[i]) continue;
    long long part=offset+i;
    ans=max(ans,part*(n-part)-m);
  }
  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/2370.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "graph/bipartitedecomposition.cpp"

#line 3 "graph/bipartitedecomposition.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(n)
struct BipartiteDecomposition{
  vector<vector<int>> G;
  BipartiteDecomposition(int n):G(n){}
  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  vector<pair<int, int>> build(){
    vector<pair<int, int>> res;
    vector<int> used(G.size(),-1);
    for(int i=0;i<(int)G.size();i++){
      if(~used[i]) continue;
      queue<int> que;
      used[i]=0;
      que.emplace(i);
      pair<int, int> cnt;
      while(!que.empty()){
        int v=que.front();que.pop();
        if(used[v]==0) cnt.first++;
        else cnt.second++;
        for(int u:G[v]){
          if(~used[u]){
            if(used[u]==used[v]) return {};
            continue;
          }
          used[u]=used[v]^1;
          que.emplace(u);
        }
      }
      res.emplace_back(cnt);
    }
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
int main(){
  return 0;
}
#endif
#line 1 "algorithm/partialsum.cpp"

#line 3 "algorithm/partialsum.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(n sqrt(n) / w)
// w: wordsize
template<size_t N>
bitset<N+1> partial_sum(vector<int> vs){
  int sum=0;
  for(int v:vs) sum+=v;
  assert(sum<=N);
  vector<int> cnt(sum+1,0);
  for(int v:vs) cnt[v]++;
  for(int i=1;i*2<=sum;i++){
    int num=(cnt[i]-1)/2;
    cnt[i]-=num*2;
    cnt[i*2]+=num;
  }
  bitset<N+1> dp;
  dp[0]=1;
  for(int i=1;i<=sum;i++)
    for(int t=0;t<cnt[i];t++)
      dp|=dp<<i;
  return dp;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/2370.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  BipartiteDecomposition G(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v);
  }
  auto res=G.build();
  if(res.empty()){
    cout<<-1<<endl;
    return 0;
  }

  int offset=0;
  vector<int> vs;
  for(auto[x,y]:res){
    offset+=min(x,y);
    vs.emplace_back(abs(x-y));
  }
  auto dp=partial_sum<100000>(vs);

  long long ans=0;
  for(int i=0;i<=n;i++){
    if(!dp[i]) continue;
    long long part=offset+i;
    ans=max(ans,part*(n-part)-m);
  }
  cout<<ans<<endl;
  return 0;
}

Back to top page