oj.uz

Submission #75427

# Submission time Handle Problem Language Result Execution time Memory
75427 2018-09-09T17:00:57 Z born2rule Duathlon (APIO18_duathlon) C++14
31 / 100
 567 ms 192284 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 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 dp[N],child[N],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)]=mp(u,v1);
		ed[mp(cno,curr)]=mp(v1,u);
		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
      }
    map<int,vi> tmp;
    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
	auto it=ed[mp(u,v1)];
	tmp[it.fi].pb(v1);
      }
    for(auto it:tmp)//s in v1, f is u, t in other
      {
	ll tmpsum=0;
	for(int x:it.se) tmpsum+=child[x];
	for(int x:it.se)
	  {
	    ans+=child[x]*(tmpsum-child[x]);//with same node as edge
	    ans+=(ll)child[x]*(ll)sz*(child[u]-tmpsum-sz);//with diff.nodes
	  }
      }
    //consider u as t
    ans+=(ll)dp[u]*sz*(ll)2;
    //for this component
    ans+=(ll)sz*(ll)(sz-1)*(sz-2);
    if(par==-1) return;
    for(int v1:tree[u])
      {
	if(v1==par) continue;
	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 141 ms 151544 KB Output is correct
2 Correct 145 ms 151544 KB Output is correct
3 Correct 145 ms 151544 KB Output is correct
4 Correct 148 ms 151544 KB Output is correct
5 Correct 251 ms 151592 KB Output is correct
6 Correct 151 ms 151592 KB Output is correct
7 Incorrect 144 ms 151592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 151544 KB Output is correct
2 Correct 145 ms 151544 KB Output is correct
3 Correct 145 ms 151544 KB Output is correct
4 Correct 148 ms 151544 KB Output is correct
5 Correct 251 ms 151592 KB Output is correct
6 Correct 151 ms 151592 KB Output is correct
7 Incorrect 144 ms 151592 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 330 ms 168792 KB Output is correct
2 Correct 321 ms 168792 KB Output is correct
3 Correct 420 ms 179628 KB Output is correct
4 Correct 368 ms 179628 KB Output is correct
5 Correct 367 ms 179628 KB Output is correct
6 Correct 448 ms 179628 KB Output is correct
7 Correct 495 ms 179628 KB Output is correct
8 Correct 466 ms 179628 KB Output is correct
9 Correct 470 ms 179628 KB Output is correct
10 Correct 407 ms 179628 KB Output is correct
11 Correct 342 ms 179628 KB Output is correct
12 Correct 341 ms 179628 KB Output is correct
13 Correct 330 ms 179628 KB Output is correct
14 Correct 344 ms 179628 KB Output is correct
15 Correct 289 ms 179628 KB Output is correct
16 Correct 274 ms 179628 KB Output is correct
17 Correct 167 ms 179628 KB Output is correct
18 Correct 171 ms 179628 KB Output is correct
19 Correct 185 ms 179628 KB Output is correct
20 Correct 178 ms 179628 KB Output is correct
21 Correct 173 ms 179628 KB Output is correct
22 Correct 197 ms 179628 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 179628 KB Output is correct
2 Correct 155 ms 179628 KB Output is correct
3 Correct 156 ms 179628 KB Output is correct
4 Correct 151 ms 179628 KB Output is correct
5 Correct 145 ms 179628 KB Output is correct
6 Correct 142 ms 179628 KB Output is correct
7 Correct 147 ms 179628 KB Output is correct
8 Correct 149 ms 179628 KB Output is correct
9 Correct 153 ms 179628 KB Output is correct
10 Correct 154 ms 179628 KB Output is correct
11 Correct 147 ms 179628 KB Output is correct
12 Correct 140 ms 179628 KB Output is correct
13 Correct 152 ms 179628 KB Output is correct
14 Correct 156 ms 179628 KB Output is correct
15 Correct 147 ms 179628 KB Output is correct
16 Correct 145 ms 179628 KB Output is correct
17 Correct 173 ms 179628 KB Output is correct
18 Correct 153 ms 179628 KB Output is correct
19 Correct 150 ms 179628 KB Output is correct
20 Correct 153 ms 179628 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 180572 KB Output is correct
2 Correct 459 ms 180648 KB Output is correct
3 Correct 427 ms 180668 KB Output is correct
4 Correct 459 ms 180668 KB Output is correct
5 Correct 464 ms 180668 KB Output is correct
6 Correct 567 ms 192284 KB Output is correct
7 Correct 481 ms 192284 KB Output is correct
8 Correct 516 ms 192284 KB Output is correct
9 Correct 457 ms 192284 KB Output is correct
10 Correct 471 ms 192284 KB Output is correct
11 Correct 458 ms 192284 KB Output is correct
12 Correct 436 ms 192284 KB Output is correct
13 Correct 453 ms 192284 KB Output is correct
14 Correct 433 ms 192284 KB Output is correct
15 Correct 371 ms 192284 KB Output is correct
16 Correct 313 ms 192284 KB Output is correct
17 Correct 450 ms 192284 KB Output is correct
18 Correct 440 ms 192284 KB Output is correct
19 Correct 414 ms 192284 KB Output is correct
20 Correct 432 ms 192284 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 192284 KB Output is correct
2 Correct 148 ms 192284 KB Output is correct
3 Incorrect 144 ms 192284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 192284 KB Output is correct
2 Correct 433 ms 192284 KB Output is correct
3 Incorrect 438 ms 192284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 151544 KB Output is correct
2 Correct 145 ms 151544 KB Output is correct
3 Correct 145 ms 151544 KB Output is correct
4 Correct 148 ms 151544 KB Output is correct
5 Correct 251 ms 151592 KB Output is correct
6 Correct 151 ms 151592 KB Output is correct
7 Incorrect 144 ms 151592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 151544 KB Output is correct
2 Correct 145 ms 151544 KB Output is correct
3 Correct 145 ms 151544 KB Output is correct
4 Correct 148 ms 151544 KB Output is correct
5 Correct 251 ms 151592 KB Output is correct
6 Correct 151 ms 151592 KB Output is correct
7 Incorrect 144 ms 151592 KB Output isn't correct
8 Halted 0 ms 0 KB -