oj.uz

Submission #1043282

# Submission time Handle Problem Language Result Execution time Memory
1043282 2024-08-04T07:44:15 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 61 ms 23176 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=2e5+5;
int const mod=1e9+7;

vector<int> adj[N];
vector<int> mem[N];
int sz[N];
bool vis[N];
bool bl=0;
int c=0;
void dfs(int node,int par){
	mem[c].push_back(node);
	vis[node]=1;
	for(int i:adj[node]){
		if(i!=par){
			if(vis[i]){
				bl=1;
				continue;
			}
			dfs(i,node);
			sz[node]+=sz[i];
		}
	}
	sz[node]++;
}

signed main(){
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < m; ++i)
	{
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int ans=0;
	for (int i = 1; i <=n; ++i)
		if(vis[i]==0){
			dfs(i,0);
			int cc=sz[i];
			ans+=cc*(cc-1)*(cc-1);
			ans+=cc*cc;
			for(int j:mem[c]){
				ans-=sz[j]*sz[j];
				ans-=(cc-sz[j])*(cc-sz[j]);
			}
			c++;
		}
	if(bl==0)
		return 0;
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 23176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 16364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -