test/aoj/0415.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:01:15+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415

Depends on

• graph/twoedgeconnectedcomponents.cpp
• tools/chminmax.cpp
• tree/diameterforvertex.cpp

Code

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

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

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../graph/twoedgeconnectedcomponents.cpp"
#include "../../tree/diameterforvertex.cpp"
#undef call_from_test

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

  using ll = long long;

  int n,m;
  cin>>n>>m;
  vector<ll> vs(n);
  for(int i=0;i<n;i++) cin>>vs[i];

  TwoEdgeConnectedComponents C(n);
  for(int i=0;i<m;i++){
    int s,t;
    cin>>s>>t;
    s--;t--;
    C.add_edge(s,t);
  }

  int k=C.build();
  vector<ll> sm(k,0);
  for(int i=0;i<n;i++)
    sm[C.blg[i]]+=vs[i];

  auto T=C.forest();

  ll ans=0;
  vector<int> used(k,-1);
  for(int i=0;i<k;i++){
    if(~used[i]) continue;
    int sz=0;
    queue<int> que;
    used[i]=sz++;
    que.emplace(i);

    vector<int> vv;
    vector<ll> ws;
    while(!que.empty()){
      int v=que.front();que.pop();
      vv.emplace_back(v);
      ws.emplace_back(sm[v]);
      for(int u:T[v]){
        if(~used[u]) continue;
        used[u]=sz++;
        que.emplace(u);
      }
    }

    DiameterForVertex<ll> H(ws);
    for(int v:vv)
      for(int u:T[v])
        if(u<v) H.add_edge(used[u],used[v]);

    chmax(ans,H.build());
  }

  cout<<ans<<endl;
  return 0;
}

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

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

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "graph/twoedgeconnectedcomponents.cpp"

#line 3 "graph/twoedgeconnectedcomponents.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// work with multigraph
struct TwoEdgeConnectedComponents{
  vector<int> ord,low,par,blg,sz;
  vector<vector<int>> G,C;

  TwoEdgeConnectedComponents(int n):
    ord(n,-1),low(n),par(n,-1),blg(n,-1),sz(n,1),G(n){}

  void add_edge(int u,int v){
    if(u==v) return;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  bool is_bridge(int u,int v){
    if(ord[u]>ord[v]) swap(u,v);
    return ord[u]<low[v];
  }

  void dfs(int v,int &pos){
    ord[v]=low[v]=pos++;
    int dup=0;
    for(int u:G[v]){
      if(u==par[v] and !dup){
        dup=1;
        continue;
      }
      if(~ord[u]){
        low[v]=min(low[v],ord[u]);
        continue;
      }
      par[u]=v;
      dfs(u,pos);
      sz[v]+=sz[u];
      low[v]=min(low[v],low[u]);
    }
  }

  void fill_component(int v){
    C[blg[v]].emplace_back(v);
    for(int u:G[v]){
      if(~blg[u] or is_bridge(u,v)) continue;
      blg[u]=blg[v];
      fill_component(u);
    }
  }

  void add_component(int v,int &k){
    if(~blg[v]) return;
    blg[v]=k++;
    C.emplace_back();
    fill_component(v);
  }

  int build(){
    int n=G.size(),pos=0;
    for(int i=0;i<n;i++)
      if(ord[i]<0) dfs(i,pos);

    int k=0;
    for(int i=0;i<n;i++) add_component(i,k);

    return k;
  }

  const vector<int>& operator[](int i)const{return C[i];}

  vector<vector<int>> forest(){
    int n=G.size(),k=C.size();
    vector<vector<int>> T(k);
    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          T[blg[v]].emplace_back(blg[u]);
    return T;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "tree/diameterforvertex.cpp"

#line 3 "tree/diameterforvertex.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct DiameterForVertex{
  vector<T> vs,dp;
  vector<vector<int> > G;
  DiameterForVertex(int n):dp(n),G(n){}
  DiameterForVertex(vector<T> vs):vs(vs),dp(vs.size()),G(vs.size()){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int &s){
    if(p<0) dp[v]=T(0);
    dp[v]+=vs[v];
    if(dp[s]<dp[v]) s=v;
    for(int u:G[v]){
      if(u==p) continue;
      dp[u]=dp[v];
      dfs(u,v,s);
    }
  }

  T build(){
    assert(!vs.empty());
    int s=0;
    dfs(s,-1,s);
    dfs(s,-1,s);
    return dp[s];
  }

  T build(vector<T> us){
    assert(us.size()==dp.size());
    vs=us;
    return build();
  }
};
//END CUT HERE
#ifndef call_from_test

// test build with argument vector<T>
signed ARC097_F(){
  int n;
  cin>>n;
  DiameterForVertex<int> G(n);
  vector<int> deg(n,0);
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G.add_edge(x,y);
    deg[x]++;
    deg[y]++;
  }

  string s;
  cin>>s;

  int cnt=(n-1)*2,num=0;
  queue<int> que;
  vector<int> dead(n,0);
  for(int i=0;i<n;i++){
    num+=(s[i]=='W');
    if((deg[i]==1) and (s[i]=='B')){
      dead[i]=1;
      que.emplace(i);
    }
  }

  while(!que.empty()){
    int v=que.front();que.pop();
    cnt-=2;
    for(int u:G.G[v]){
      if(dead[u]) continue;
      deg[u]--;
      if(deg[u]==1 and (s[u]=='B')){
        dead[u]=1;
        que.emplace(u);
      }
    }
  }

  if(num<=1){
    cout<<num<<endl;
    return 0;
  }

  vector<int> vs(n,0);
  for(int i=0;i<n;i++){
    if(dead[i]) continue;
    vs[i]=deg[i]+(s[i]=='W');
    vs[i]%=2;
    cnt+=vs[i];
  }

  cout<<cnt-G.build(vs)*2<<endl;
  return 0;
}
/*
  verified on 2019/12/27
  https://atcoder.jp/contests/arc097/tasks/arc097_d
*/

signed main(){
  //ARC097_F();
  return 0;
}
#endif
#line 10 "test/aoj/0415.test.cpp"
#undef call_from_test

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

  using ll = long long;

  int n,m;
  cin>>n>>m;
  vector<ll> vs(n);
  for(int i=0;i<n;i++) cin>>vs[i];

  TwoEdgeConnectedComponents C(n);
  for(int i=0;i<m;i++){
    int s,t;
    cin>>s>>t;
    s--;t--;
    C.add_edge(s,t);
  }

  int k=C.build();
  vector<ll> sm(k,0);
  for(int i=0;i<n;i++)
    sm[C.blg[i]]+=vs[i];

  auto T=C.forest();

  ll ans=0;
  vector<int> used(k,-1);
  for(int i=0;i<k;i++){
    if(~used[i]) continue;
    int sz=0;
    queue<int> que;
    used[i]=sz++;
    que.emplace(i);

    vector<int> vv;
    vector<ll> ws;
    while(!que.empty()){
      int v=que.front();que.pop();
      vv.emplace_back(v);
      ws.emplace_back(sm[v]);
      for(int u:T[v]){
        if(~used[u]) continue;
        used[u]=sz++;
        que.emplace(u);
      }
    }

    DiameterForVertex<ll> H(ws);
    for(int v:vv)
      for(int u:T[v])
        if(u<v) H.add_edge(used[u],used[v]);

    chmax(ans,H.build());
  }

  cout<<ans<<endl;
  return 0;
}

Back to top page