답안 #75406 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75406	2018-09-09T15:29:13 Z	born2rule	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	399 ms	177800 KB

count_triplets

#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,int par=-1)
  {
    vis[u]=true;
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	dfstree2(v1,u);
	sumd[u]+=sumd[v1];
	sumd2[u]+=sumd2[v1];
      }
    int sz=sz(nodes[u]);
    for(int v1:tree[u])
      {
	if(v1==par) 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);
      }
    //trace(u,ans,"dasDSa");
    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;
  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

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	151416 KB	Output is correct
2	Correct	149 ms	151712 KB	Output is correct
3	Correct	148 ms	151764 KB	Output is correct
4	Correct	152 ms	151764 KB	Output is correct
5	Correct	152 ms	151764 KB	Output is correct
6	Correct	155 ms	151764 KB	Output is correct
7	Incorrect	150 ms	151764 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	151416 KB	Output is correct
2	Correct	149 ms	151712 KB	Output is correct
3	Correct	148 ms	151764 KB	Output is correct
4	Correct	152 ms	151764 KB	Output is correct
5	Correct	152 ms	151764 KB	Output is correct
6	Correct	155 ms	151764 KB	Output is correct
7	Incorrect	150 ms	151764 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	311 ms	169272 KB	Output is correct
2	Correct	297 ms	169272 KB	Output is correct
3	Correct	343 ms	171656 KB	Output is correct
4	Correct	336 ms	171656 KB	Output is correct
5	Correct	322 ms	171656 KB	Output is correct
6	Correct	357 ms	171656 KB	Output is correct
7	Correct	341 ms	171656 KB	Output is correct
8	Correct	395 ms	171656 KB	Output is correct
9	Correct	365 ms	171656 KB	Output is correct
10	Correct	323 ms	171656 KB	Output is correct
11	Correct	307 ms	171656 KB	Output is correct
12	Correct	316 ms	171656 KB	Output is correct
13	Correct	285 ms	171656 KB	Output is correct
14	Correct	287 ms	171656 KB	Output is correct
15	Correct	303 ms	171656 KB	Output is correct
16	Correct	259 ms	171656 KB	Output is correct
17	Correct	179 ms	171656 KB	Output is correct
18	Correct	192 ms	171656 KB	Output is correct
19	Correct	174 ms	171656 KB	Output is correct
20	Correct	174 ms	171656 KB	Output is correct
21	Correct	168 ms	171656 KB	Output is correct
22	Correct	176 ms	171656 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	150 ms	171656 KB	Output is correct
2	Correct	143 ms	171656 KB	Output is correct
3	Correct	151 ms	171656 KB	Output is correct
4	Correct	160 ms	171656 KB	Output is correct
5	Correct	154 ms	171656 KB	Output is correct
6	Correct	151 ms	171656 KB	Output is correct
7	Correct	146 ms	171656 KB	Output is correct
8	Correct	150 ms	171656 KB	Output is correct
9	Correct	146 ms	171656 KB	Output is correct
10	Correct	146 ms	171656 KB	Output is correct
11	Correct	147 ms	171656 KB	Output is correct
12	Correct	153 ms	171656 KB	Output is correct
13	Correct	144 ms	171656 KB	Output is correct
14	Correct	154 ms	171656 KB	Output is correct
15	Correct	150 ms	171656 KB	Output is correct
16	Correct	151 ms	171656 KB	Output is correct
17	Correct	148 ms	171656 KB	Output is correct
18	Correct	154 ms	171656 KB	Output is correct
19	Correct	144 ms	171656 KB	Output is correct
20	Correct	149 ms	171656 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	311 ms	171656 KB	Output is correct
2	Correct	323 ms	171656 KB	Output is correct
3	Correct	323 ms	171656 KB	Output is correct
4	Correct	311 ms	171656 KB	Output is correct
5	Correct	312 ms	171656 KB	Output is correct
6	Correct	335 ms	177800 KB	Output is correct
7	Correct	355 ms	177800 KB	Output is correct
8	Correct	370 ms	177800 KB	Output is correct
9	Correct	344 ms	177800 KB	Output is correct
10	Correct	326 ms	177800 KB	Output is correct
11	Correct	326 ms	177800 KB	Output is correct
12	Correct	353 ms	177800 KB	Output is correct
13	Correct	335 ms	177800 KB	Output is correct
14	Correct	303 ms	177800 KB	Output is correct
15	Correct	322 ms	177800 KB	Output is correct
16	Correct	292 ms	177800 KB	Output is correct
17	Correct	265 ms	177800 KB	Output is correct
18	Correct	271 ms	177800 KB	Output is correct
19	Correct	299 ms	177800 KB	Output is correct
20	Correct	311 ms	177800 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	147 ms	177800 KB	Output is correct
2	Correct	157 ms	177800 KB	Output is correct
3	Incorrect	156 ms	177800 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	369 ms	177800 KB	Output is correct
2	Correct	342 ms	177800 KB	Output is correct
3	Incorrect	399 ms	177800 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	151416 KB	Output is correct
2	Correct	149 ms	151712 KB	Output is correct
3	Correct	148 ms	151764 KB	Output is correct
4	Correct	152 ms	151764 KB	Output is correct
5	Correct	152 ms	151764 KB	Output is correct
6	Correct	155 ms	151764 KB	Output is correct
7	Incorrect	150 ms	151764 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	151416 KB	Output is correct
2	Correct	149 ms	151712 KB	Output is correct
3	Correct	148 ms	151764 KB	Output is correct
4	Correct	152 ms	151764 KB	Output is correct
5	Correct	152 ms	151764 KB	Output is correct
6	Correct	155 ms	151764 KB	Output is correct
7	Incorrect	150 ms	151764 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

답안 #75406

Compilation message