oj.uz

Submission #75398

# Submission time Handle Problem Language Result Execution time Memory
75398 2018-09-09T14:58:20 Z born2rule Duathlon (APIO18_duathlon) C++14
36 / 100
 1000 ms 171468 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=100005;
  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)
  {
    vis[u]=true;
    for(int v1:tree[u])
      {
	if(vis[v1]) continue;
	dfstree2(v1);
	sumd[u]+=sumd[v1];
	sumd2[u]+=sumd2[v1];
      }
    int sz=sz(nodes[u]);
    for(int v1:tree[u])
      {
	if(vis[v1]) 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);
      }
    ll tmp=0;
    //add answer for root
    tmp+=(ll)sz*sumd[u];
    tmp-=((ll)(child[u]-sz)*(ll)sz*(ll)(d[u]+2-sz));
    //remove answer for corner point
    tmp-=sz*sumd2[u];
    tmp+=((ll)(child2[u]-1)*(ll)sz*(ll)(d[u]+2-sz));
    //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));
    //add answer when both corner points
    tmp+=(sumd2[u]-(child[u]-sz));
    tmp-=((ll)(child2[u]-1)*(ll)d[u]);
    ans+=tmp*(ll)2;
    //add answer for within the node
    ans+=(ll)sz*(sz-1)*(sz-2);
    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;
  rep(i,1,n+1)
    {
      if(bt::vis[i]) continue;
      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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 77048 KB Output is correct
2 Correct 72 ms 77180 KB Output is correct
3 Correct 73 ms 77240 KB Output is correct
4 Correct 72 ms 77240 KB Output is correct
5 Correct 73 ms 77240 KB Output is correct
6 Correct 72 ms 77240 KB Output is correct
7 Correct 73 ms 77240 KB Output is correct
8 Correct 73 ms 77332 KB Output is correct
9 Correct 86 ms 77332 KB Output is correct
10 Correct 388 ms 77348 KB Output is correct
11 Correct 73 ms 77384 KB Output is correct
12 Correct 71 ms 77384 KB Output is correct
13 Correct 74 ms 77384 KB Output is correct
14 Correct 72 ms 77432 KB Output is correct
15 Correct 72 ms 77432 KB Output is correct
16 Correct 74 ms 77432 KB Output is correct
17 Correct 74 ms 77432 KB Output is correct
18 Correct 96 ms 77432 KB Output is correct
19 Correct 75 ms 77432 KB Output is correct
20 Correct 72 ms 77432 KB Output is correct
21 Correct 72 ms 77432 KB Output is correct
22 Correct 94 ms 77432 KB Output is correct
23 Correct 76 ms 77432 KB Output is correct
24 Correct 74 ms 77432 KB Output is correct
25 Correct 74 ms 77432 KB Output is correct
26 Correct 86 ms 77432 KB Output is correct
27 Correct 72 ms 77432 KB Output is correct
28 Correct 84 ms 77432 KB Output is correct
29 Correct 75 ms 77432 KB Output is correct
30 Correct 80 ms 77432 KB Output is correct
31 Correct 71 ms 77432 KB Output is correct
32 Correct 78 ms 77432 KB Output is correct
33 Correct 71 ms 77432 KB Output is correct
34 Correct 74 ms 77432 KB Output is correct
35 Correct 75 ms 77432 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 77048 KB Output is correct
2 Correct 72 ms 77180 KB Output is correct
3 Correct 73 ms 77240 KB Output is correct
4 Correct 72 ms 77240 KB Output is correct
5 Correct 73 ms 77240 KB Output is correct
6 Correct 72 ms 77240 KB Output is correct
7 Correct 73 ms 77240 KB Output is correct
8 Correct 73 ms 77332 KB Output is correct
9 Correct 86 ms 77332 KB Output is correct
10 Correct 388 ms 77348 KB Output is correct
11 Correct 73 ms 77384 KB Output is correct
12 Correct 71 ms 77384 KB Output is correct
13 Correct 74 ms 77384 KB Output is correct
14 Correct 72 ms 77432 KB Output is correct
15 Correct 72 ms 77432 KB Output is correct
16 Correct 74 ms 77432 KB Output is correct
17 Correct 74 ms 77432 KB Output is correct
18 Correct 96 ms 77432 KB Output is correct
19 Correct 75 ms 77432 KB Output is correct
20 Correct 72 ms 77432 KB Output is correct
21 Correct 72 ms 77432 KB Output is correct
22 Correct 94 ms 77432 KB Output is correct
23 Correct 76 ms 77432 KB Output is correct
24 Correct 74 ms 77432 KB Output is correct
25 Correct 74 ms 77432 KB Output is correct
26 Correct 86 ms 77432 KB Output is correct
27 Correct 72 ms 77432 KB Output is correct
28 Correct 84 ms 77432 KB Output is correct
29 Correct 75 ms 77432 KB Output is correct
30 Correct 80 ms 77432 KB Output is correct
31 Correct 71 ms 77432 KB Output is correct
32 Correct 78 ms 77432 KB Output is correct
33 Correct 71 ms 77432 KB Output is correct
34 Correct 74 ms 77432 KB Output is correct
35 Correct 75 ms 77432 KB Output is correct
36 Correct 74 ms 77432 KB Output is correct
37 Correct 74 ms 77432 KB Output is correct
38 Correct 99 ms 77432 KB Output is correct
39 Execution timed out 1077 ms 77432 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 95360 KB Output is correct
2 Correct 220 ms 95372 KB Output is correct
3 Correct 195 ms 95372 KB Output is correct
4 Correct 206 ms 95372 KB Output is correct
5 Correct 183 ms 95372 KB Output is correct
6 Correct 187 ms 95372 KB Output is correct
7 Correct 196 ms 95372 KB Output is correct
8 Correct 182 ms 95372 KB Output is correct
9 Correct 182 ms 95372 KB Output is correct
10 Correct 181 ms 95372 KB Output is correct
11 Correct 178 ms 95372 KB Output is correct
12 Correct 168 ms 95372 KB Output is correct
13 Correct 161 ms 95372 KB Output is correct
14 Correct 163 ms 95372 KB Output is correct
15 Correct 144 ms 95372 KB Output is correct
16 Correct 140 ms 95372 KB Output is correct
17 Correct 79 ms 95372 KB Output is correct
18 Correct 77 ms 95372 KB Output is correct
19 Correct 74 ms 95372 KB Output is correct
20 Correct 79 ms 95372 KB Output is correct
21 Correct 78 ms 95372 KB Output is correct
22 Correct 77 ms 95372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 95372 KB Output is correct
2 Correct 72 ms 95372 KB Output is correct
3 Correct 73 ms 95372 KB Output is correct
4 Correct 74 ms 95372 KB Output is correct
5 Correct 76 ms 95372 KB Output is correct
6 Correct 75 ms 95372 KB Output is correct
7 Correct 71 ms 95372 KB Output is correct
8 Correct 72 ms 95372 KB Output is correct
9 Correct 73 ms 95372 KB Output is correct
10 Correct 74 ms 95372 KB Output is correct
11 Correct 80 ms 95372 KB Output is correct
12 Correct 75 ms 95372 KB Output is correct
13 Correct 71 ms 95372 KB Output is correct
14 Correct 76 ms 95372 KB Output is correct
15 Correct 75 ms 95372 KB Output is correct
16 Correct 74 ms 95372 KB Output is correct
17 Correct 76 ms 95372 KB Output is correct
18 Correct 71 ms 95372 KB Output is correct
19 Correct 73 ms 95372 KB Output is correct
20 Correct 70 ms 95372 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 95372 KB Output is correct
2 Correct 192 ms 95372 KB Output is correct
3 Correct 185 ms 95372 KB Output is correct
4 Correct 195 ms 95372 KB Output is correct
5 Correct 192 ms 95372 KB Output is correct
6 Correct 223 ms 95372 KB Output is correct
7 Correct 205 ms 95372 KB Output is correct
8 Correct 203 ms 95372 KB Output is correct
9 Correct 180 ms 95372 KB Output is correct
10 Correct 195 ms 95372 KB Output is correct
11 Correct 173 ms 95372 KB Output is correct
12 Correct 188 ms 95372 KB Output is correct
13 Correct 183 ms 95372 KB Output is correct
14 Correct 167 ms 95372 KB Output is correct
15 Correct 166 ms 95372 KB Output is correct
16 Correct 133 ms 95372 KB Output is correct
17 Correct 151 ms 95372 KB Output is correct
18 Correct 148 ms 95372 KB Output is correct
19 Correct 151 ms 95372 KB Output is correct
20 Correct 159 ms 95372 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 95372 KB Output is correct
2 Correct 78 ms 95372 KB Output is correct
3 Incorrect 75 ms 95372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 95372 KB Output is correct
2 Correct 212 ms 95372 KB Output is correct
3 Runtime error 269 ms 171468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 77048 KB Output is correct
2 Correct 72 ms 77180 KB Output is correct
3 Correct 73 ms 77240 KB Output is correct
4 Correct 72 ms 77240 KB Output is correct
5 Correct 73 ms 77240 KB Output is correct
6 Correct 72 ms 77240 KB Output is correct
7 Correct 73 ms 77240 KB Output is correct
8 Correct 73 ms 77332 KB Output is correct
9 Correct 86 ms 77332 KB Output is correct
10 Correct 388 ms 77348 KB Output is correct
11 Correct 73 ms 77384 KB Output is correct
12 Correct 71 ms 77384 KB Output is correct
13 Correct 74 ms 77384 KB Output is correct
14 Correct 72 ms 77432 KB Output is correct
15 Correct 72 ms 77432 KB Output is correct
16 Correct 74 ms 77432 KB Output is correct
17 Correct 74 ms 77432 KB Output is correct
18 Correct 96 ms 77432 KB Output is correct
19 Correct 75 ms 77432 KB Output is correct
20 Correct 72 ms 77432 KB Output is correct
21 Correct 72 ms 77432 KB Output is correct
22 Correct 94 ms 77432 KB Output is correct
23 Correct 76 ms 77432 KB Output is correct
24 Correct 74 ms 77432 KB Output is correct
25 Correct 74 ms 77432 KB Output is correct
26 Correct 86 ms 77432 KB Output is correct
27 Correct 72 ms 77432 KB Output is correct
28 Correct 84 ms 77432 KB Output is correct
29 Correct 75 ms 77432 KB Output is correct
30 Correct 80 ms 77432 KB Output is correct
31 Correct 71 ms 77432 KB Output is correct
32 Correct 78 ms 77432 KB Output is correct
33 Correct 71 ms 77432 KB Output is correct
34 Correct 74 ms 77432 KB Output is correct
35 Correct 75 ms 77432 KB Output is correct
36 Correct 74 ms 77432 KB Output is correct
37 Correct 74 ms 77432 KB Output is correct
38 Correct 99 ms 77432 KB Output is correct
39 Execution timed out 1077 ms 77432 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 77048 KB Output is correct
2 Correct 72 ms 77180 KB Output is correct
3 Correct 73 ms 77240 KB Output is correct
4 Correct 72 ms 77240 KB Output is correct
5 Correct 73 ms 77240 KB Output is correct
6 Correct 72 ms 77240 KB Output is correct
7 Correct 73 ms 77240 KB Output is correct
8 Correct 73 ms 77332 KB Output is correct
9 Correct 86 ms 77332 KB Output is correct
10 Correct 388 ms 77348 KB Output is correct
11 Correct 73 ms 77384 KB Output is correct
12 Correct 71 ms 77384 KB Output is correct
13 Correct 74 ms 77384 KB Output is correct
14 Correct 72 ms 77432 KB Output is correct
15 Correct 72 ms 77432 KB Output is correct
16 Correct 74 ms 77432 KB Output is correct
17 Correct 74 ms 77432 KB Output is correct
18 Correct 96 ms 77432 KB Output is correct
19 Correct 75 ms 77432 KB Output is correct
20 Correct 72 ms 77432 KB Output is correct
21 Correct 72 ms 77432 KB Output is correct
22 Correct 94 ms 77432 KB Output is correct
23 Correct 76 ms 77432 KB Output is correct
24 Correct 74 ms 77432 KB Output is correct
25 Correct 74 ms 77432 KB Output is correct
26 Correct 86 ms 77432 KB Output is correct
27 Correct 72 ms 77432 KB Output is correct
28 Correct 84 ms 77432 KB Output is correct
29 Correct 75 ms 77432 KB Output is correct
30 Correct 80 ms 77432 KB Output is correct
31 Correct 71 ms 77432 KB Output is correct
32 Correct 78 ms 77432 KB Output is correct
33 Correct 71 ms 77432 KB Output is correct
34 Correct 74 ms 77432 KB Output is correct
35 Correct 75 ms 77432 KB Output is correct
36 Correct 74 ms 77432 KB Output is correct
37 Correct 74 ms 77432 KB Output is correct
38 Correct 99 ms 77432 KB Output is correct
39 Execution timed out 1077 ms 77432 KB Time limit exceeded
40 Halted 0 ms 0 KB -