oj.uz

Submission #99839

# Submission time Handle Problem Language Result Execution time Memory
99839 2019-03-07T18:51:01 Z TadijaSebez Duathlon (APIO18_duathlon) C++11
0 / 100
 238 ms 32608 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];
}
void Solve(int u, int p)
{
	for(int v:E[u]) if(v!=p) Solve(v,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)(n-1)*dep[p]*2;
    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]);
	}
	//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);
	//for(int i=n+1;i<=cnt;i++) ans+=(ll)csz[i]*(csz[i]-1)*n*2-(ll)csz[i]*(csz[i]-1)*(csz[i]-2);
	printf("%lld\n",ans);
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:69: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:71: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 126 ms 29548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 23136 KB Output is correct
2 Correct 189 ms 24320 KB Output is correct
3 Correct 199 ms 24220 KB Output is correct
4 Correct 185 ms 24184 KB Output is correct
5 Correct 232 ms 24224 KB Output is correct
6 Correct 182 ms 32608 KB Output is correct
7 Correct 183 ms 29692 KB Output is correct
8 Correct 238 ms 28376 KB Output is correct
9 Correct 167 ms 27000 KB Output is correct
10 Incorrect 189 ms 24288 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 23212 KB Output is correct
2 Correct 195 ms 24124 KB Output is correct
3 Incorrect 198 ms 23672 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 -