답안 #92503 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92503	2019-01-03T06:31:26 Z	antimirage	철인 이종 경기 (APIO18_duathlon)	C++14	8 / 100	85 ms	11000 KB

count_triplets

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e5 + 5;

int n, m, x, y, u[N];
long long cn;

vector < vector <int> > g;

long long ans;

bool fl;

void dfs (int v, int p = 0)
{
	cn++;
	u[v] = 1;
	for (auto to : g[v])
	{
		if (u[to] && to != p) fl = 1;
		
		if (u[to]) continue;
		dfs(to, v);
	}
}

main() 
{
	cin >> n >> m;
	g.resize(n + 1);
	
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if (u[i]) continue;
		cn = 0;
		fl = false;
		dfs(i);
		if (fl)
			ans += cn * 1ll * (cn - 1) * (cn - 2);
		else
			ans += cn * 1ll * (cn - 1) * (cn - 2) / 3;
	}
	cout << ans << endl;
}

Compilation message

count_triplets.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() 
      ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Incorrect	2 ms	256 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Incorrect	2 ms	256 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	10872 KB	Output is correct
2	Correct	72 ms	10868 KB	Output is correct
3	Correct	51 ms	8696 KB	Output is correct
4	Correct	52 ms	11000 KB	Output is correct
5	Correct	50 ms	8992 KB	Output is correct
6	Correct	51 ms	9080 KB	Output is correct
7	Correct	50 ms	8440 KB	Output is correct
8	Correct	60 ms	8824 KB	Output is correct
9	Correct	85 ms	7928 KB	Output is correct
10	Correct	78 ms	8340 KB	Output is correct
11	Correct	60 ms	7288 KB	Output is correct
12	Correct	55 ms	7160 KB	Output is correct
13	Correct	44 ms	7032 KB	Output is correct
14	Correct	47 ms	7032 KB	Output is correct
15	Correct	33 ms	6392 KB	Output is correct
16	Correct	37 ms	6264 KB	Output is correct
17	Correct	5 ms	3064 KB	Output is correct
18	Correct	5 ms	3064 KB	Output is correct
19	Correct	4 ms	3064 KB	Output is correct
20	Correct	5 ms	3064 KB	Output is correct
21	Correct	5 ms	3064 KB	Output is correct
22	Correct	5 ms	3064 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	68 ms	6268 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	60 ms	6360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Incorrect	2 ms	256 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Incorrect	2 ms	256 KB	Output isn't correct
8	Halted	0 ms	0 KB	-