oj.uz

Submission #982210

# Submission time Handle Problem Language Result Execution time Memory
982210 2024-05-14T02:58:26 Z Faisal_Saqib Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
vector<int> ma[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);
		}
	}
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int j=0;j<m;j++)
	{
		int x,y;
		cin>>x>>y;
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	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<<ans<<endl;
}
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
	solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 536 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 536 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 Execution timed out 1056 ms 1048576 KB Time limit exceeded
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 4956 KB Output is correct
3 Correct 2 ms 5084 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 5084 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 5024 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 2 ms 5156 KB Output is correct
17 Correct 1 ms 4956 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 29 ms 9300 KB Output is correct
2 Correct 28 ms 9504 KB Output is correct
3 Correct 29 ms 9816 KB Output is correct
4 Correct 30 ms 9564 KB Output is correct
5 Correct 28 ms 9488 KB Output is correct
6 Correct 35 ms 13556 KB Output is correct
7 Correct 34 ms 12124 KB Output is correct
8 Correct 34 ms 11344 KB Output is correct
9 Correct 31 ms 10836 KB Output is correct
10 Correct 28 ms 9296 KB Output is correct
11 Correct 38 ms 9300 KB Output is correct
12 Correct 28 ms 9532 KB Output is correct
13 Correct 29 ms 9296 KB Output is correct
14 Correct 35 ms 9300 KB Output is correct
15 Correct 27 ms 8960 KB Output is correct
16 Correct 16 ms 8028 KB Output is correct
17 Correct 21 ms 9672 KB Output is correct
18 Correct 22 ms 9812 KB Output is correct
19 Correct 21 ms 9668 KB Output is correct
20 Correct 31 ms 9864 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Runtime error 614 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 36 ms 9564 KB Output is correct
2 Correct 29 ms 9304 KB Output is correct
3 Runtime error 711 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 536 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 536 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -