oj.uz

Submission #75423

# Submission time Handle Problem Language Result Execution time Memory
75423 2018-09-09T16:49:49 Z born2rule Duathlon (APIO18_duathlon) C++14
18 / 100
 550 ms 186268 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,dp[N],child[N];//dp is no. of s,f pairs in its subtree
  map<ii,ii> ed;
  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);
		ed[mp(curr,cno)]=ed[mp(cno,curr)]=mp(u,v1);
		dfs(v1);
	      }
	    else
	      {
		Q[curr].push(v1);
		nodes[curr].pb(v1);
		vis[v1]=true;
	      }
	  }
      }
  }
  void dfstree(int u)
  {
    child[u]=sz(nodes[u]);
    vis[u]=true;
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	dfstree(v1);
	child[u]+=child[v1];
      }
  }
  void dfstree2(int u,int par=-1)
  {
    vis[u]=true;
    int sz=sz(nodes[u]);
    for(int v1:tree[u])
      {
	if(v1==par) continue;
	dfstree2(v1,u);
	dp[u]+=dp[v1];//f,s pairs of its children
      }
    for(int v1:tree[u])
      {
	if(v1==par) continue;
	ans+=(dp[u]-dp[v1])*(ll)child[v1];//s in v1 and f,t in other comp.
	ans+=(ll)(child[u]-child[v1]-sz)*dp[v1];//t in other comp, and s,f in v1
	ans+=(ll)child[v1]*(ll)(child[u]-child[v1]-sz);//s in v1, f is u, t in other comp.
      }
    //consider u as t
    ans+=(ll)dp[u]*sz*(ll)2;
    //for this component
    ans+=(ll)sz*(ll)(sz-1)*(sz-2);
    for(int v1:tree[u])
      {
	if(v1==par) continue;
	if(par==-1) return;
	auto it1=ed[mp(u,v1)],it2=ed[mp(u,par)];
	//consider it as f
	if(it1.fi!=it2.fi && it1.fi!=it2.se && it1.se!=it2.fi && it1.se!=it2.se)//diff. incoming and outgoing node
	  dp[u]+=(ll)child[v1]*sz;
	else
	  dp[u]+=child[v1];
      }
    dp[u]+=(ll)(sz-1)*(sz-1);
  }
};
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;
  bt::cno=0;
  rep(i,1,n+1)
    {
      if(bt::vis[i]) continue;
      ++bt::cno;
      bt::dfs(i);
    }
  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 146 ms 151672 KB Output is correct
2 Correct 158 ms 151676 KB Output is correct
3 Correct 147 ms 151676 KB Output is correct
4 Correct 147 ms 151676 KB Output is correct
5 Correct 148 ms 151676 KB Output is correct
6 Correct 143 ms 151676 KB Output is correct
7 Incorrect 145 ms 151772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 151672 KB Output is correct
2 Correct 158 ms 151676 KB Output is correct
3 Correct 147 ms 151676 KB Output is correct
4 Correct 147 ms 151676 KB Output is correct
5 Correct 148 ms 151676 KB Output is correct
6 Correct 143 ms 151676 KB Output is correct
7 Incorrect 145 ms 151772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 168408 KB Output is correct
2 Correct 313 ms 168408 KB Output is correct
3 Correct 402 ms 175124 KB Output is correct
4 Correct 360 ms 175124 KB Output is correct
5 Correct 370 ms 175124 KB Output is correct
6 Correct 448 ms 175204 KB Output is correct
7 Correct 427 ms 175204 KB Output is correct
8 Correct 442 ms 175204 KB Output is correct
9 Correct 478 ms 175204 KB Output is correct
10 Correct 400 ms 175204 KB Output is correct
11 Correct 332 ms 175204 KB Output is correct
12 Correct 336 ms 175204 KB Output is correct
13 Correct 313 ms 175204 KB Output is correct
14 Correct 315 ms 175204 KB Output is correct
15 Correct 310 ms 175204 KB Output is correct
16 Correct 355 ms 175204 KB Output is correct
17 Correct 218 ms 175204 KB Output is correct
18 Correct 201 ms 175204 KB Output is correct
19 Correct 182 ms 175204 KB Output is correct
20 Correct 194 ms 175204 KB Output is correct
21 Correct 173 ms 175204 KB Output is correct
22 Correct 199 ms 175204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 175204 KB Output is correct
2 Correct 149 ms 175204 KB Output is correct
3 Correct 149 ms 175204 KB Output is correct
4 Correct 156 ms 175204 KB Output is correct
5 Correct 146 ms 175204 KB Output is correct
6 Correct 150 ms 175204 KB Output is correct
7 Correct 147 ms 175204 KB Output is correct
8 Correct 153 ms 175204 KB Output is correct
9 Correct 148 ms 175204 KB Output is correct
10 Correct 160 ms 175204 KB Output is correct
11 Correct 146 ms 175204 KB Output is correct
12 Correct 152 ms 175204 KB Output is correct
13 Correct 154 ms 175204 KB Output is correct
14 Correct 151 ms 175204 KB Output is correct
15 Correct 147 ms 175204 KB Output is correct
16 Correct 144 ms 175204 KB Output is correct
17 Correct 151 ms 175204 KB Output is correct
18 Correct 152 ms 175204 KB Output is correct
19 Correct 165 ms 175204 KB Output is correct
20 Correct 148 ms 175204 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 179712 KB Output is correct
2 Correct 438 ms 179836 KB Output is correct
3 Correct 435 ms 179836 KB Output is correct
4 Correct 435 ms 179844 KB Output is correct
5 Correct 437 ms 179912 KB Output is correct
6 Incorrect 550 ms 186268 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 186268 KB Output is correct
2 Correct 149 ms 186268 KB Output is correct
3 Incorrect 145 ms 186268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 186268 KB Output is correct
2 Correct 420 ms 186268 KB Output is correct
3 Incorrect 402 ms 186268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 151672 KB Output is correct
2 Correct 158 ms 151676 KB Output is correct
3 Correct 147 ms 151676 KB Output is correct
4 Correct 147 ms 151676 KB Output is correct
5 Correct 148 ms 151676 KB Output is correct
6 Correct 143 ms 151676 KB Output is correct
7 Incorrect 145 ms 151772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 151672 KB Output is correct
2 Correct 158 ms 151676 KB Output is correct
3 Correct 147 ms 151676 KB Output is correct
4 Correct 147 ms 151676 KB Output is correct
5 Correct 148 ms 151676 KB Output is correct
6 Correct 143 ms 151676 KB Output is correct
7 Incorrect 145 ms 151772 KB Output isn't correct
8 Halted 0 ms 0 KB -