oj.uz

Submission #408083

# Submission time Handle Problem Language Result Execution time Memory
408083 2021-05-19T05:53:55 Z juggernaut Duathlon (APIO18_duathlon) C++17
8 / 100
 102 ms 10516 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m;
vector<int>g[100005];
ll ans;
bool circle;
bool vis[100005];
int sz;
void dfs(int v,int p){
	vis[v]=true;
	sz++;
	for(int to:g[v])if(to!=p){
		if(vis[to]){
			circle=true;
			continue;
		}
		dfs(to,v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		circle=false;
		sz=0;
		dfs(i,i);
		ll s=sz*1ll;
		if(circle)ans+=s*(s-1)*(s-2);
		else for(int i=1;i<=sz;i++)ans+=2ll*(i-1)*(1ll*(sz-i));
	}
	printf("%lld",ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Incorrect 2 ms 2636 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 102 ms 10516 KB Output is correct
2 Correct 77 ms 10484 KB Output is correct
3 Correct 74 ms 8180 KB Output is correct
4 Correct 92 ms 9884 KB Output is correct
5 Correct 96 ms 7932 KB Output is correct
6 Correct 64 ms 7900 KB Output is correct
7 Correct 76 ms 7300 KB Output is correct
8 Correct 86 ms 7604 KB Output is correct
9 Correct 65 ms 6836 KB Output is correct
10 Correct 92 ms 7192 KB Output is correct
11 Correct 64 ms 6320 KB Output is correct
12 Correct 64 ms 6212 KB Output is correct
13 Correct 68 ms 6180 KB Output is correct
14 Correct 55 ms 6108 KB Output is correct
15 Correct 43 ms 5708 KB Output is correct
16 Correct 36 ms 5676 KB Output is correct
17 Correct 3 ms 2656 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 3 ms 2760 KB Output is correct
21 Correct 4 ms 2652 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 5840 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 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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