oj.uz

Submission #99850

# Submission time Handle Problem Language Result Execution time Memory
99850 2019-03-07T20:44:54 Z TadijaSebez Duathlon (APIO18_duathlon) C++11
23 / 100
 284 ms 36728 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
vector<int> G[N],E[N];
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
int cnt,disc[N],low[N],tid,n,csz[N];
bool in[N];
stack<int> s;
void Tarjan(int u)
{
	disc[u]=low[u]=++tid;
	in[u]=1;s.push(u);
	for(int v:G[u])
	{
		if(!disc[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=disc[u])
			{
				++cnt;
				AddEdge(u,cnt);
				csz[cnt]++;
				int h;
				do
				{
					h=s.top();
					s.pop();
					in[h]=0;
					AddEdge(h,cnt);
					csz[cnt]++;
				}while(h!=v);
			}
		}
		else if(in[v]) low[u]=min(low[u],disc[v]);
	}
}
ll ans;
int sz[N],dep[N],up[N];
void DFSSZ(int u, int p)
{
	sz[u]=u<=n;
	dep[u]=dep[p]+(u<=n);
	up[u]=n;
	for(int v:E[u]) if(v!=p) DFSSZ(v,u),sz[u]+=sz[v],up[u]-=sz[v];
}
int rt[N],par[N];
ll all[N],up_all[N],down_all[N];
void Solve(int u, int p, int root)
{
	par[u]=p;
	all[u]=(ll)(sz[root]-(u<=n))*(sz[root]-(u<=n)-1);
	all[u]-=(ll)(sz[root]-sz[u])*(sz[root]-sz[u]-1);
	for(int v:E[u]) if(v!=p) all[u]-=(ll)sz[v]*(sz[v]-1);
	down_all[u]=(ll)(sz[u]-(u<=n))*(sz[u]-(u<=n)-1);
	for(int v:E[u]) if(v!=p) down_all[u]-=(ll)sz[v]*(sz[v]-1);
	if(p)
	{
		up_all[u]=all[p];
		up_all[u]-=(ll)(sz[root]-(p<=n))*(sz[root]-(p<=n)-1);
		up_all[u]+=(ll)(sz[root]-sz[u]-(p<=n))*(sz[root]-sz[u]-(p<=n)-1);
		up_all[u]+=(ll)sz[u]*(sz[u]-1);
	}
	for(int v:E[u]) if(v!=p) Solve(v,u,root);
	if(u<=n)
	{
		ans+=all[u];
		//for(int v:E[u]) if(v!=p) ans+=down_all[v];
		//if(p) ans+=up_all[u];
	}
	//printf("u:%i ans:%lld all:%lld up_all:%lld down_all:%lld\n",u,ans,all[u],up_all[u],down_all[u]);
	/*ll all=(ll)sz[u]*(sz[u]-1);
	int ch=0;
	for(int v:E[u]) if(v!=p) all-=(ll)sz[v]*(sz[v]-1),ch+=csz[v]-1;
	if(u<=n) ans+=(ll)(sz[root]-1)*dep[p]*2;
	ans-=all*(dep[u]+dep[p]);
	//else ans-=all*(dep[u]+dep[p]);
	//printf("all:%lld\n",all);
	/*if(u<=n)
	{
		if(p) ans-=(ll)sz[u]*(csz[p]-1)*2*2;
		ans-=(ll)up[u]*ch*2*2;
		//printf("u:%i ans:%lld sz:%i up:%i dep:%i ch:%i csz[p]:%i\n",u,ans,sz[u],up[u],dep[u],ch,csz[p]);
	}*//*
	if(u>n)
	{
		//ans-=(ll)sz[root]*(csz[u]-1)*4;
		ans+=(ll)(sz[root]-csz[u])*(csz[u]-1)*(csz[u]-2)*2;
		ans+=(ll)csz[u]*(csz[u]-1)*(csz[u]-2);
		for(int v:E[u]) if(v!=p)
		{
			//ans-=(ll)(sz[u]-sz[v]);
			ans+=(ll)(sz[root]-sz[v]-csz[u]+1)*(sz[v]-1)*(csz[u]-2);
		}
		ans+=(ll)(sz[root]-up[p]-csz[u]+1)*(up[p]-1)*(csz[u]-2);
	}
	rt[u]=root;
	//else printf("u:%i ans:%i\n",u,ans);*/
}
int main()
{
	int m,u,v;
	scanf("%i %i",&n,&m);
	cnt=n;
	for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
	vector<int> root;
	for(int i=1;i<=n;i++) if(!disc[i]) Tarjan(i),root.pb(i);
	for(int i:root) DFSSZ(i,0),Solve(i,0,i);
	//for(int i=n+1;i<=cnt;i++) ans+=(ll)csz[i]*(csz[i]-1)*sz[rt[i]]*2-(ll)csz[i]*(csz[i]-1)*(csz[i]-2);
	printf("%lld\n",ans);
	return 0;
}

Compilation message

count_triplets.cpp:81:2: warning: "/*" within comment [-Wcomment]
  /*if(u<=n)
   
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:107:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 32140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 12 ms 9984 KB Output is correct
4 Correct 12 ms 10112 KB Output is correct
5 Correct 12 ms 10036 KB Output is correct
6 Correct 13 ms 9984 KB Output is correct
7 Correct 14 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 10 ms 9984 KB Output is correct
10 Correct 12 ms 9984 KB Output is correct
11 Correct 11 ms 9984 KB Output is correct
12 Correct 11 ms 9984 KB Output is correct
13 Correct 11 ms 9980 KB Output is correct
14 Correct 12 ms 9984 KB Output is correct
15 Correct 12 ms 9984 KB Output is correct
16 Correct 11 ms 9856 KB Output is correct
17 Correct 11 ms 9984 KB Output is correct
18 Correct 12 ms 9984 KB Output is correct
19 Correct 12 ms 9956 KB Output is correct
20 Correct 10 ms 9984 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 28400 KB Output is correct
2 Correct 205 ms 28524 KB Output is correct
3 Correct 182 ms 28408 KB Output is correct
4 Correct 199 ms 28388 KB Output is correct
5 Correct 191 ms 28508 KB Output is correct
6 Correct 216 ms 36728 KB Output is correct
7 Correct 284 ms 33856 KB Output is correct
8 Correct 268 ms 32456 KB Output is correct
9 Correct 231 ms 31136 KB Output is correct
10 Correct 224 ms 28424 KB Output is correct
11 Correct 213 ms 28536 KB Output is correct
12 Correct 207 ms 28408 KB Output is correct
13 Correct 279 ms 28536 KB Output is correct
14 Correct 272 ms 27640 KB Output is correct
15 Correct 170 ms 26744 KB Output is correct
16 Correct 130 ms 23412 KB Output is correct
17 Correct 204 ms 28984 KB Output is correct
18 Correct 162 ms 29012 KB Output is correct
19 Correct 166 ms 29336 KB Output is correct
20 Correct 188 ms 29120 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9984 KB Output is correct
2 Correct 14 ms 9956 KB Output is correct
3 Incorrect 12 ms 10028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 28380 KB Output is correct
2 Correct 222 ms 28504 KB Output is correct
3 Incorrect 225 ms 27128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -