oj.uz

Submission #982300

# Submission time Handle Problem Language Result Execution time Memory
982300 2024-05-14T06:10:16 Z Faisal_Saqib Duathlon (APIO18_duathlon) C++17
23 / 100
 715 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N=1e5+10;
vector<int> ma[N];
// ll pre[N];
bool vis[N];
ll ans=0,sz[N],dp[N],dp_[N];
void dfs(int x,int p=-1)
{
	sz[x]=1;
	vis[x]=1;
	for(auto y:ma[x])
	{
		if(y!=p)
		{
			dfs(y,x);
			sz[x]+=sz[y];
			dp[x]-=(sz[y]*sz[y]);
		}
	}
	dp[x]+=((sz[x]-1)*(sz[x]-1));
}
void ChangeRoot(int x,int y)
{
	// 
	dp[x]+=(sz[y]*sz[y]);
	dp[x]-=((sz[x]-1)*(sz[x]-1));
	dp[y]-=((sz[y]-1)*(sz[y]-1));
	sz[x]-=sz[y];
	sz[y]+=sz[x];
	dp[x]+=((sz[x]-1)*(sz[x]-1));
	dp[y]+=((sz[y]-1)*(sz[y]-1));
	dp[y]-=(sz[x]*sz[x]);
}
void dfs_(int x,int p=-1)
{
	vis[x]=1;
	ans+=dp[x];
	for(auto y:ma[x])
	{
		if(y!=p)
		{			
			ChangeRoot(x,y);
			dfs_(y,x);
			ChangeRoot(y,x);
		}
	}
}
bool cycle=0;
int nodes=0;
void _dfs(int x,int p=-1)
{
	vis[x]=1;
	nodes++;
	for(auto y:ma[x])
	{
		if(y!=p)
		{
			if(vis[y])
			{
				cycle=1;
			}
			else
			{
				_dfs(y,x);
			}
		}
	}
}
int f_cyc(int x)
{
	return (x*(x-1)*(x-2))/6;
}
// int f_lin(int x)
// {
// 	ll cur=(x-1)*(x-1)*(x-1);
// 	return cur-(pre[x-1]);
// }
int f_lin_brute(int x)
{
	ll ans=0;
	ll sp=(x-1)*(x-1);
	for(int j=1;j<=x;j++)
		ans+=(sp-((j-1)*(j-1))-((x-j)*(x-j)));
	return ans;
}
void solve()
{
	// int n,m;
	// cin>>n;
	// // m=n-1;
	int n,m;
	cin>>n>>m;
	vector<int> deg(n+2);
	for(int i=0;i<m;i++)
	{
		int x=i+1,y=i+2;
		cin>>x>>y;
		deg[x]++;
		deg[y]++;
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	int mx=0;
	for(int i=1;i<=n;i++)
		mx=max(mx,deg[i]);
	if(mx<=2)
	{
		// Solve a Cycle or a Path
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				cycle=0;
				nodes=0;
				_dfs(i);
				if(cycle)
				{
					ans+=f_cyc(nodes);
				}
				else
				{
					ans+=f_lin_brute(nodes);
				}
			}
		}
	}
	else
	{
		// Solve on Tree	
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				dfs(i);
			}
		}
		for(int i=1;i<=n;i++)
			vis[i]=0;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				dfs_(i);
			}
		}
	}
	// cout<<"Hola amigo "<<f_lin(n)<<endl;
	// cout<<f_lin_brute(n)<<endl;
	cout<<ans<<endl;
}
signed main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  // pre[0]=0;
  // ll asp=1e5+1;
  // for(int i=1;i<=asp;i++)
  // 	pre[i]=pre[i-1]+(i*i);
  solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 715 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 715 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 11608 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 1 ms 4956 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 1 ms 5028 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 1 ms 5208 KB Output is correct
17 Correct 1 ms 4952 KB Output is correct
18 Correct 1 ms 4956 KB Output is correct
19 Correct 1 ms 4956 KB Output is correct
20 Correct 1 ms 4956 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9556 KB Output is correct
2 Correct 32 ms 9760 KB Output is correct
3 Correct 40 ms 9424 KB Output is correct
4 Correct 39 ms 9428 KB Output is correct
5 Correct 30 ms 9560 KB Output is correct
6 Correct 27 ms 9296 KB Output is correct
7 Correct 43 ms 12356 KB Output is correct
8 Correct 33 ms 11608 KB Output is correct
9 Correct 32 ms 10784 KB Output is correct
10 Correct 30 ms 9556 KB Output is correct
11 Correct 32 ms 9560 KB Output is correct
12 Correct 31 ms 9560 KB Output is correct
13 Correct 31 ms 9564 KB Output is correct
14 Correct 28 ms 9308 KB Output is correct
15 Correct 29 ms 9048 KB Output is correct
16 Correct 18 ms 8296 KB Output is correct
17 Correct 22 ms 9672 KB Output is correct
18 Correct 22 ms 9544 KB Output is correct
19 Correct 23 ms 9920 KB Output is correct
20 Correct 22 ms 9536 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Runtime error 617 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9552 KB Output is correct
2 Correct 33 ms 9296 KB Output is correct
3 Runtime error 676 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 715 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 715 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -