oj.uz

Submission #99849

# Submission time Handle Problem Language Result Execution time Memory
99849 2019-03-07T20:34:01 Z TadijaSebez Duathlon (APIO18_duathlon) C++11
0 / 100
 271 ms 36796 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)(up[u]-(u<=n))*(up[u]-(u<=n)-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 11 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 32212 KB Output is correct
2 Correct 139 ms 32216 KB Output is correct
3 Incorrect 178 ms 31252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9916 KB Output is correct
2 Correct 11 ms 9884 KB Output is correct
3 Correct 14 ms 9984 KB Output is correct
4 Correct 11 ms 10112 KB Output is correct
5 Correct 11 ms 10112 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 10 ms 9984 KB Output is correct
8 Correct 13 ms 9984 KB Output is correct
9 Correct 12 ms 9984 KB Output is correct
10 Incorrect 10 ms 9984 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 28444 KB Output is correct
2 Correct 197 ms 28536 KB Output is correct
3 Correct 192 ms 28508 KB Output is correct
4 Correct 183 ms 28408 KB Output is correct
5 Correct 192 ms 28420 KB Output is correct
6 Correct 228 ms 36796 KB Output is correct
7 Correct 220 ms 33912 KB Output is correct
8 Correct 235 ms 32604 KB Output is correct
9 Correct 218 ms 31224 KB Output is correct
10 Incorrect 204 ms 28408 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 10 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 11 ms 9984 KB Output is correct
6 Correct 13 ms 9856 KB Output is correct
7 Correct 12 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 13 ms 9984 KB Output is correct
10 Correct 12 ms 9856 KB Output is correct
11 Correct 13 ms 9964 KB Output is correct
12 Correct 13 ms 10112 KB Output is correct
13 Correct 13 ms 9984 KB Output is correct
14 Correct 11 ms 9984 KB Output is correct
15 Correct 10 ms 9984 KB Output is correct
16 Incorrect 14 ms 9984 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 28660 KB Output is correct
2 Correct 212 ms 28444 KB Output is correct
3 Correct 226 ms 27172 KB Output is correct
4 Correct 270 ms 27012 KB Output is correct
5 Correct 186 ms 25208 KB Output is correct
6 Correct 178 ms 24412 KB Output is correct
7 Correct 174 ms 24184 KB Output is correct
8 Correct 156 ms 23628 KB Output is correct
9 Correct 152 ms 23372 KB Output is correct
10 Correct 163 ms 23340 KB Output is correct
11 Correct 148 ms 23284 KB Output is correct
12 Correct 171 ms 23024 KB Output is correct
13 Correct 159 ms 23160 KB Output is correct
14 Correct 141 ms 25512 KB Output is correct
15 Correct 270 ms 34424 KB Output is correct
16 Correct 271 ms 32504 KB Output is correct
17 Correct 264 ms 32776 KB Output is correct
18 Correct 250 ms 30840 KB Output is correct
19 Incorrect 199 ms 27128 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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