oj.uz

Submission #99851

# Submission time Handle Problem Language Result Execution time Memory
99851 2019-03-07T20:45:32 Z TadijaSebez Duathlon (APIO18_duathlon) C++11
23 / 100
 232 ms 36744 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 10 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 10 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 141 ms 32244 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 10 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 13 ms 10108 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 15 ms 9984 KB Output is correct
7 Correct 12 ms 10112 KB Output is correct
8 Correct 14 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 13 ms 9984 KB Output is correct
11 Correct 12 ms 9984 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9984 KB Output is correct
14 Correct 12 ms 9984 KB Output is correct
15 Correct 11 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 9956 KB Output is correct
19 Correct 12 ms 9984 KB Output is correct
20 Correct 12 ms 9984 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 28416 KB Output is correct
2 Correct 220 ms 28480 KB Output is correct
3 Correct 232 ms 28408 KB Output is correct
4 Correct 184 ms 28536 KB Output is correct
5 Correct 189 ms 28408 KB Output is correct
6 Correct 216 ms 36744 KB Output is correct
7 Correct 229 ms 34020 KB Output is correct
8 Correct 213 ms 32504 KB Output is correct
9 Correct 202 ms 31124 KB Output is correct
10 Correct 193 ms 28408 KB Output is correct
11 Correct 181 ms 28408 KB Output is correct
12 Correct 184 ms 28476 KB Output is correct
13 Correct 217 ms 28488 KB Output is correct
14 Correct 181 ms 27640 KB Output is correct
15 Correct 166 ms 26752 KB Output is correct
16 Correct 110 ms 23444 KB Output is correct
17 Correct 197 ms 29092 KB Output is correct
18 Correct 160 ms 29040 KB Output is correct
19 Correct 151 ms 29164 KB Output is correct
20 Correct 150 ms 29120 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 28516 KB Output is correct
2 Correct 185 ms 28280 KB Output is correct
3 Incorrect 218 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 10 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 10 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -