oj.uz

Submission #408577

# Submission time Handle Problem Language Result Execution time Memory
408577 2021-05-19T08:25:45 Z juggernaut Duathlon (APIO18_duathlon) C++17
8 / 100
 97 ms 11868 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 ans+=s*(s-1)*(s-2)/3;
	}
	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 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 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 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 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 82 ms 10476 KB Output is correct
2 Correct 97 ms 11868 KB Output is correct
3 Correct 55 ms 9364 KB Output is correct
4 Correct 97 ms 10584 KB Output is correct
5 Correct 75 ms 8676 KB Output is correct
6 Correct 57 ms 8624 KB Output is correct
7 Correct 59 ms 8032 KB Output is correct
8 Correct 69 ms 8316 KB Output is correct
9 Correct 52 ms 7492 KB Output is correct
10 Correct 66 ms 7884 KB Output is correct
11 Correct 45 ms 6868 KB Output is correct
12 Correct 46 ms 6744 KB Output is correct
13 Correct 60 ms 6604 KB Output is correct
14 Correct 47 ms 6544 KB Output is correct
15 Correct 37 ms 5972 KB Output is correct
16 Correct 31 ms 5844 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 4 ms 2764 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 3 ms 2636 KB Output is correct
21 Correct 3 ms 2636 KB Output is correct
22 Correct 3 ms 2652 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 55 ms 5888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 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 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 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 -