oj.uz

Submission #99845

# Submission time Handle Problem Language Result Execution time Memory
99845 2019-03-07T19:34:06 Z TadijaSebez Duathlon (APIO18_duathlon) C++11
31 / 100
 244 ms 32120 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];
void Solve(int u, int p, int root)
{
	for(int v:E[u]) if(v!=p) Solve(v,u,root);
	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;
	if(u<=n) ans-=all*(dep[u]+dep[p]);
	else ans-=all*(dep[u]+dep[p]-1);
	//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]);
	}
	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: In function 'int main()':
count_triplets.cpp:79: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:81: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 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Incorrect 9 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 29904 KB Output is correct
2 Correct 122 ms 29784 KB Output is correct
3 Correct 163 ms 27740 KB Output is correct
4 Correct 170 ms 28336 KB Output is correct
5 Correct 132 ms 24700 KB Output is correct
6 Correct 142 ms 26740 KB Output is correct
7 Correct 164 ms 24668 KB Output is correct
8 Correct 170 ms 25176 KB Output is correct
9 Correct 169 ms 23268 KB Output is correct
10 Correct 165 ms 23416 KB Output is correct
11 Correct 173 ms 21228 KB Output is correct
12 Correct 135 ms 21004 KB Output is correct
13 Correct 121 ms 20924 KB Output is correct
14 Correct 125 ms 20596 KB Output is correct
15 Correct 105 ms 19828 KB Output is correct
16 Correct 103 ms 19700 KB Output is correct
17 Correct 16 ms 13048 KB Output is correct
18 Correct 17 ms 13048 KB Output is correct
19 Correct 17 ms 13048 KB Output is correct
20 Correct 16 ms 13048 KB Output is correct
21 Correct 16 ms 13048 KB Output is correct
22 Correct 19 ms 13048 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 23816 KB Output is correct
2 Correct 195 ms 23760 KB Output is correct
3 Correct 164 ms 23672 KB Output is correct
4 Correct 174 ms 23980 KB Output is correct
5 Correct 162 ms 23908 KB Output is correct
6 Correct 181 ms 32120 KB Output is correct
7 Correct 213 ms 29304 KB Output is correct
8 Correct 244 ms 27888 KB Output is correct
9 Correct 199 ms 26488 KB Output is correct
10 Correct 183 ms 23800 KB Output is correct
11 Correct 197 ms 23800 KB Output is correct
12 Correct 170 ms 23800 KB Output is correct
13 Correct 173 ms 23684 KB Output is correct
14 Correct 168 ms 23156 KB Output is correct
15 Correct 144 ms 22452 KB Output is correct
16 Correct 94 ms 19892 KB Output is correct
17 Correct 136 ms 24304 KB Output is correct
18 Correct 130 ms 24304 KB Output is correct
19 Correct 151 ms 24556 KB Output is correct
20 Correct 140 ms 24312 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9856 KB Output is correct
2 Correct 10 ms 9856 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 183 ms 23780 KB Output is correct
2 Correct 151 ms 23576 KB Output is correct
3 Incorrect 196 ms 22832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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