oj.uz

Submission #75404

# Submission time Handle Problem Language Result Execution time Memory
75404 2018-09-09T15:18:55 Z born2rule Duathlon (APIO18_duathlon) C++14
0 / 100
 401 ms 171752 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005;
vi v[N];
bool vis[N];
ll ans;
int n,m;
//for subtask 1,2
bool mark[N];
//for subtask 4,5
ll sumd[N]; int d[N],child[N];
bool checksub12()
{
  if(n>50) return false;
  function<void (int,int,int,vi&) > dfs = [&](int u,int s,int f,vi &tmp)->void
    {
      if(u==f)
	{
	  for(int x:tmp) mark[x]=true;
	  return;
	}
      vis[u]=true;
      tmp.pb(u);
      for(int v1:v[u]) if(!vis[v1]) dfs(v1,s,f,tmp);
      tmp.pop_back();
      vis[u]=false;
    };
  rep(i,1,n+1)
    rep(j,i+1,n+1)
    {
      rep(k,1,n+1) mark[k]=false;
      vi tmp;
      dfs(i,i,j,tmp);
      rep(k,1,n+1)
	if(k!=i && k!=j && mark[k]) ans+=2;
    }
  cout<<ans<<endl;
  return true;
}
bool checksub3()
{
  bool sub3=true;
  rep(i,1,n+1) if(sz(v[i])>2) sub3=false;
  if(!sub3) return false;
  function<void (int, vi&)> dfs = [&](int u,vi &tmp)->void
    {
      vis[u]=true; tmp.pb(u);
      for(int v1:v[u]) if(!vis[v1]) dfs(v1,tmp);
    };
  memset(vis,false,sizeof(vis));
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      vi tmp;
      dfs(i,tmp);
      bool chain=false;
      for(int x:tmp) if(sz(v[x])==1) chain=true;
      int tot=sz(tmp);
      if(!chain) ans+=(ll)(tot-2)*(ll)tot*(tot-1);
      else rep(j,1,tot-1) ans+=((ll)j*(j+1));
    }
  cout<<ans<<endl;
  return true;
}
bool checksub45()
{
  function<bool (int, int)> dfs = [&](int u,int par)->bool
    {
      child[u]=1;
      vis[u]=true;
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  if(vis[v1]) return false;
	  d[v1]=d[u]+1;
	  dfs(v1,u);
	  child[u]+=child[v1];
	}
      return true;
    };
  function<void (int, int)> dfs2 = [&](int u,int par)->void
    {
      vis[u]=true;
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  dfs2(v1,u);
	  sumd[u]+=sumd[v1];
	}
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  ans+=(ll)(child[u]-child[v1]-1)*(ll)sumd[v1];
	  ans+=(ll)child[v1]*(ll)(sumd[u]-sumd[v1]);
	  ans-=(ll)child[v1]*(child[u]-(ll)child[v1]-1)*(ll)(d[u]*2+1);
	}
      ans+=(ll)(sumd[u]-(ll)(child[u]-1)*(ll)(d[u]+1))*(ll)2;
      sumd[u]+=d[u];
    };
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      if(!dfs(i,-1)) return false;
    }
  memset(vis,false,sizeof(vis));
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      dfs2(i,-1);
    }
  cout<<ans<<endl;
  return true;
}
namespace bt//bridge tree
{
  const int N=200005;
  vi v[N],tree[N],nodes[N];
  int a[N],b[N],low[N],st[N],d[N],timer,cno=1,child[N],child2[N];
  ll sumd[N],sumd2[N];
  bool bridge[N],vis[N],mark[N];
  queue<int> Q[N];
  ll ans=0;
  void findbridges(int u,int par=-1)
  {
    vis[u]=true;
    low[u]=st[u]=timer++;
    for(int ind:v[u])
      {
	if(ind==par) continue;
	int v1=(a[ind]^b[ind]^u);
	if(vis[v1]) low[u]=min(low[u],st[v1]);
	else
	  {
	    findbridges(v1,ind);
	    low[u]=min(low[u],low[v1]);
	    if(low[v1]>st[u])
	      bridge[ind]=true;
	  }
      }
  }
  void dfs(int u)
  {
    int curr=cno;
    Q[curr].push(u);
    nodes[curr].pb(u);
    vis[u]=true;
    while(!Q[curr].empty())
      {
	u=Q[curr].front();
	Q[curr].pop();
	for(int ind:v[u])
	  {
	    if(mark[ind]) continue;
	    int v1=(a[ind]^b[ind]^u);
	    mark[ind]=true;
	    if(vis[v1])
	      continue;
	    if(bridge[ind])
	      {
		cno++;
		tree[curr].pb(cno);
		tree[cno].pb(curr);
		dfs(v1);
	      }
	    else
	      {
		Q[curr].push(v1);
		nodes[curr].pb(v1);
		vis[v1]=true;
	      }
	  }
      }
  }
  void dfstree(int u)
  {
    child[u]=sz(nodes[u]);
    child2[u]=1;
    d[u]+=sz(nodes[u]);
    vis[u]=true;
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	d[v1]+=d[u];
	dfstree(v1);
	child[u]+=child[v1];
	child2[u]+=child2[v1];
      }
  }
  void dfstree2(int u)
  {
    vis[u]=true;
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	dfstree2(v1);
	sumd[u]+=sumd[v1];
	sumd2[u]+=sumd2[v1];
      }
    int sz=sz(nodes[u]);
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	ans+=(ll)(child[u]-child[v1]-sz)*(ll)sumd[v1];
	ans+=(ll)child[v1]*(ll)(sumd[u]-sumd[v1]);
	ans-=(ll)child[v1]*(child[u]-(ll)child[v1]-sz)*(ll)(d[u]*2+2-sz);
	//remove answer for corner points
	ans-=(ll)(child[u]-child[v1]-sz)*sumd2[v1];
	ans-=(ll)child2[v1]*(ll)(sumd[u]-sumd[v1]);
	ans+=(ll)child2[v1]*(child[u]-(ll)child[v1]-sz)*(ll)(d[u]*2+2-sz);
	//add answer when v1's corner point,but not on other
	ans+=(ll)(child[u]-child[v1]-sz-(child2[u]-child2[v1]-1))*(ll)(sumd2[v1]-child[v1]);
	ans+=(ll)child2[v1]*(ll)(sumd[u]-sumd[v1]-(sumd2[u]-sumd2[v1]));
	ans-=(ll)child2[v1]*(ll)(child[u]-child[v1]-sz-(child2[u]-child2[v1]-1))*(ll)(d[u]*2+1-sz);
	//add answer when both corner points
	ans+=(ll)(child2[u]-child2[v1]-1)*(ll)(sumd2[v1]-child[v1]);
	ans+=(ll)child2[v1]*(ll)(sumd2[u]-sumd2[v1]-(child[u]-child[v1]-sz));
	ans-=(ll)child2[v1]*(ll)(child2[u]-child2[v1]-1)*(ll)(d[u]*2-sz);
      }
    ll tmp=0;
    //add answer for root
    tmp+=(ll)sz*sumd[u];
    tmp-=((ll)(child[u]-sz)*(ll)sz*(ll)(d[u]+2-sz));
    //if(u==2) trace(tmp);
    //remove answer for corner point
    tmp-=sz*sumd2[u];
    tmp+=((ll)(child2[u]-1)*(ll)sz*(ll)(d[u]+2-sz));
    //if(u==2) trace(tmp);
    //add answer when v1's corner point,but not on other
    tmp+=(ll)(sz-1)*(sumd2[u]-(child[u]-sz));
    tmp-=((ll)(child2[u]-1)*(ll)(sz-1)*(ll)(d[u]+1-sz));
    //if(u==2) trace(tmp);
    //add answer when both corner points
    tmp+=(sumd2[u]-(child[u]-sz));
    tmp-=((ll)(child2[u]-1)*(ll)d[u]);
    //if(u==2) trace(tmp,sumd2[u],child[u],child2[u]);
    ans+=tmp*(ll)2;
    //add answer for within the node
    ans+=(ll)sz*(ll)(sz-1)*(ll)(sz-2);
    //trace(u,ans);
    sumd[u]+=(ll)d[u]*sz;
    sumd2[u]+=d[u];
  }
};
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  cin>>n>>m;
  rep(i,1,m+1)
    {
      int x,y;
      cin>>x>>y;
      v[x].pb(y); v[y].pb(x);
      bt::a[i]=x; bt::b[i]=y;
      bt::v[x].pb(i); bt::v[y].pb(i);
    }
  //if(checksub12()) return 0;//brute
  //if(checksub45()) return 0;// a tree
  //if(checksub3()) return 0; //degree at most 2
  rep(i,1,n+1)
    {
      if(bt::vis[i]) continue;
      bt::findbridges(i);
    }
  rep(i,1,n+1) bt::vis[i]=false;
  rep(i,1,n+1)
    {
      if(bt::vis[i]) continue;
      bt::dfs(i);
      int ind=-1;
      rep(j,i+1,n+1)
	{
	  if(!bt::vis[j])
	    {
	      ind=j;
	      break;
	    }
	}
      if(ind==-1) break;
      i=ind-1;
      ++bt::cno;
    }
  rep(i,1,n+1) bt::vis[i]=false;
  rep(i,1,n+1)
    {
      if(bt::vis[i]) continue;
      bt::dfstree(i);
    }
  rep(i,1,n+1) bt::vis[i]=false;
  rep(i,1,bt::cno+1)
    {
      if(bt::vis[i]) continue;
      bt::dfstree2(i);
    }
  cout<<bt::ans<<endl;
  return 0 ;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 151492 KB Output is correct
2 Correct 143 ms 151548 KB Output is correct
3 Correct 139 ms 151592 KB Output is correct
4 Correct 140 ms 151668 KB Output is correct
5 Correct 153 ms 151668 KB Output is correct
6 Correct 148 ms 151668 KB Output is correct
7 Incorrect 148 ms 151776 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 151492 KB Output is correct
2 Correct 143 ms 151548 KB Output is correct
3 Correct 139 ms 151592 KB Output is correct
4 Correct 140 ms 151668 KB Output is correct
5 Correct 153 ms 151668 KB Output is correct
6 Correct 148 ms 151668 KB Output is correct
7 Incorrect 148 ms 151776 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 169264 KB Output is correct
2 Correct 309 ms 169328 KB Output is correct
3 Incorrect 292 ms 171752 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 171752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 171752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 171752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 171752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 151492 KB Output is correct
2 Correct 143 ms 151548 KB Output is correct
3 Correct 139 ms 151592 KB Output is correct
4 Correct 140 ms 151668 KB Output is correct
5 Correct 153 ms 151668 KB Output is correct
6 Correct 148 ms 151668 KB Output is correct
7 Incorrect 148 ms 151776 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 151492 KB Output is correct
2 Correct 143 ms 151548 KB Output is correct
3 Correct 139 ms 151592 KB Output is correct
4 Correct 140 ms 151668 KB Output is correct
5 Correct 153 ms 151668 KB Output is correct
6 Correct 148 ms 151668 KB Output is correct
7 Incorrect 148 ms 151776 KB Output isn't correct
8 Halted 0 ms 0 KB -