oj.uz

Submission #75431

# Submission time Handle Problem Language Result Execution time Memory
75431 2018-09-09T17:07:54 Z born2rule Duathlon (APIO18_duathlon) C++14
66 / 100
 527 ms 205944 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);
    //f,t is u
    ans+=((ll)(child[u]-sz)*(ll)(sz-1)*(ll)(sz-1))*(ll)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 145 ms 151420 KB Output is correct
2 Correct 145 ms 151564 KB Output is correct
3 Correct 143 ms 151592 KB Output is correct
4 Correct 166 ms 151592 KB Output is correct
5 Correct 143 ms 151600 KB Output is correct
6 Correct 146 ms 151652 KB Output is correct
7 Correct 142 ms 151652 KB Output is correct
8 Incorrect 140 ms 151652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 151420 KB Output is correct
2 Correct 145 ms 151564 KB Output is correct
3 Correct 143 ms 151592 KB Output is correct
4 Correct 166 ms 151592 KB Output is correct
5 Correct 143 ms 151600 KB Output is correct
6 Correct 146 ms 151652 KB Output is correct
7 Correct 142 ms 151652 KB Output is correct
8 Incorrect 140 ms 151652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 168900 KB Output is correct
2 Correct 310 ms 168900 KB Output is correct
3 Correct 423 ms 179768 KB Output is correct
4 Correct 397 ms 179768 KB Output is correct
5 Correct 375 ms 179768 KB Output is correct
6 Correct 450 ms 179768 KB Output is correct
7 Correct 489 ms 179768 KB Output is correct
8 Correct 465 ms 179768 KB Output is correct
9 Correct 456 ms 179768 KB Output is correct
10 Correct 446 ms 179768 KB Output is correct
11 Correct 339 ms 179768 KB Output is correct
12 Correct 338 ms 179768 KB Output is correct
13 Correct 324 ms 179768 KB Output is correct
14 Correct 324 ms 179768 KB Output is correct
15 Correct 288 ms 179768 KB Output is correct
16 Correct 291 ms 179768 KB Output is correct
17 Correct 176 ms 179768 KB Output is correct
18 Correct 177 ms 179768 KB Output is correct
19 Correct 166 ms 179768 KB Output is correct
20 Correct 187 ms 179768 KB Output is correct
21 Correct 168 ms 179768 KB Output is correct
22 Correct 165 ms 179768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 179768 KB Output is correct
2 Correct 146 ms 179768 KB Output is correct
3 Correct 146 ms 179768 KB Output is correct
4 Correct 143 ms 179768 KB Output is correct
5 Correct 144 ms 179768 KB Output is correct
6 Correct 209 ms 179768 KB Output is correct
7 Correct 144 ms 179768 KB Output is correct
8 Correct 144 ms 179768 KB Output is correct
9 Correct 144 ms 179768 KB Output is correct
10 Correct 141 ms 179768 KB Output is correct
11 Correct 139 ms 179768 KB Output is correct
12 Correct 244 ms 179768 KB Output is correct
13 Correct 156 ms 179768 KB Output is correct
14 Correct 143 ms 179768 KB Output is correct
15 Correct 194 ms 179768 KB Output is correct
16 Correct 153 ms 179768 KB Output is correct
17 Correct 143 ms 179768 KB Output is correct
18 Correct 146 ms 179768 KB Output is correct
19 Correct 153 ms 179768 KB Output is correct
20 Correct 169 ms 179768 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 180512 KB Output is correct
2 Correct 480 ms 180540 KB Output is correct
3 Correct 435 ms 180540 KB Output is correct
4 Correct 428 ms 180540 KB Output is correct
5 Correct 471 ms 180540 KB Output is correct
6 Correct 527 ms 192252 KB Output is correct
7 Correct 471 ms 192252 KB Output is correct
8 Correct 458 ms 192252 KB Output is correct
9 Correct 472 ms 192252 KB Output is correct
10 Correct 437 ms 192252 KB Output is correct
11 Correct 440 ms 192252 KB Output is correct
12 Correct 442 ms 192252 KB Output is correct
13 Correct 427 ms 192252 KB Output is correct
14 Correct 405 ms 192252 KB Output is correct
15 Correct 380 ms 192252 KB Output is correct
16 Correct 306 ms 192252 KB Output is correct
17 Correct 411 ms 192252 KB Output is correct
18 Correct 405 ms 192252 KB Output is correct
19 Correct 401 ms 192252 KB Output is correct
20 Correct 442 ms 192252 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 192252 KB Output is correct
2 Correct 143 ms 192252 KB Output is correct
3 Correct 147 ms 192252 KB Output is correct
4 Correct 145 ms 192252 KB Output is correct
5 Correct 142 ms 192252 KB Output is correct
6 Correct 149 ms 192252 KB Output is correct
7 Correct 143 ms 192252 KB Output is correct
8 Correct 140 ms 192252 KB Output is correct
9 Correct 142 ms 192252 KB Output is correct
10 Correct 148 ms 192252 KB Output is correct
11 Correct 149 ms 192252 KB Output is correct
12 Correct 147 ms 192252 KB Output is correct
13 Correct 141 ms 192252 KB Output is correct
14 Correct 141 ms 192252 KB Output is correct
15 Correct 140 ms 192252 KB Output is correct
16 Correct 144 ms 192252 KB Output is correct
17 Correct 151 ms 192252 KB Output is correct
18 Correct 143 ms 192252 KB Output is correct
19 Correct 143 ms 192252 KB Output is correct
20 Correct 143 ms 192252 KB Output is correct
21 Correct 148 ms 192252 KB Output is correct
22 Correct 142 ms 192252 KB Output is correct
23 Correct 186 ms 192252 KB Output is correct
24 Correct 148 ms 192252 KB Output is correct
25 Correct 145 ms 192252 KB Output is correct
26 Correct 142 ms 192252 KB Output is correct
27 Correct 144 ms 192252 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 192252 KB Output is correct
2 Correct 404 ms 192252 KB Output is correct
3 Correct 418 ms 192252 KB Output is correct
4 Correct 370 ms 192252 KB Output is correct
5 Correct 315 ms 192252 KB Output is correct
6 Correct 312 ms 192252 KB Output is correct
7 Correct 332 ms 192252 KB Output is correct
8 Correct 278 ms 192252 KB Output is correct
9 Correct 292 ms 192252 KB Output is correct
10 Correct 299 ms 192252 KB Output is correct
11 Correct 272 ms 192252 KB Output is correct
12 Correct 301 ms 192252 KB Output is correct
13 Correct 310 ms 192252 KB Output is correct
14 Correct 294 ms 192252 KB Output is correct
15 Correct 444 ms 197448 KB Output is correct
16 Correct 516 ms 197448 KB Output is correct
17 Correct 409 ms 197448 KB Output is correct
18 Correct 422 ms 197448 KB Output is correct
19 Correct 379 ms 197448 KB Output is correct
20 Correct 369 ms 197448 KB Output is correct
21 Correct 378 ms 197448 KB Output is correct
22 Correct 354 ms 197448 KB Output is correct
23 Correct 329 ms 197448 KB Output is correct
24 Correct 425 ms 204484 KB Output is correct
25 Correct 411 ms 205944 KB Output is correct
26 Correct 394 ms 205944 KB Output is correct
27 Correct 374 ms 205944 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 151420 KB Output is correct
2 Correct 145 ms 151564 KB Output is correct
3 Correct 143 ms 151592 KB Output is correct
4 Correct 166 ms 151592 KB Output is correct
5 Correct 143 ms 151600 KB Output is correct
6 Correct 146 ms 151652 KB Output is correct
7 Correct 142 ms 151652 KB Output is correct
8 Incorrect 140 ms 151652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 151420 KB Output is correct
2 Correct 145 ms 151564 KB Output is correct
3 Correct 143 ms 151592 KB Output is correct
4 Correct 166 ms 151592 KB Output is correct
5 Correct 143 ms 151600 KB Output is correct
6 Correct 146 ms 151652 KB Output is correct
7 Correct 142 ms 151652 KB Output is correct
8 Incorrect 140 ms 151652 KB Output isn't correct
9 Halted 0 ms 0 KB -