답안 #75427 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75427	2018-09-09T17:00:57 Z	born2rule	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	567 ms	192284 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;//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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #75427

Compilation message