Submission #387817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387817	2021-04-09T08:54:05 Z	milleniumEeee	Duathlon (APIO18_duathlon)	C++14	13 / 100	167 ms	12304 KB

count_triplets

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define int long long
using namespace std;

const int MAXN = (int)1e5 + 5;

vector <int> g[MAXN];

int n, m;
int S, C, F;
bool used[MAXN];

bool dfs(int v) {
	used[v] = 1;
	if (v == F) {
		used[v] = 0;
		if (!used[C]) {
			return false;
		} else {
			return true;
		}
	}
	bool found = false;
	for (int to : g[v]) {
		if (!used[to]) {
			found |= dfs(to);
			if (found) {
				used[v] = 0;
				return true;
			}
		}
	}
	used[v] = 0;
	return false;
}

void subtask1() {
	int ans = 0;
	for (int s = 1; s <= n; s++) {
		for (int c = 1; c <= n; c++) {
			for (int f = 1; f <= n; f++) {
				if (s != c && s != f && c != f) {
					S = s;
					C = c;
					F = f;
					if (dfs(s)) {
						ans++;
					}
				}
			}
		}
	}
	cout << ans << endl;	
	exit(0);
}

bool cycle(int v, int par = -1) {
	used[v] = 1;
	bool f = 0;
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		if (!used[to]) {
			f |= cycle(to, v);
		} 
		else if (used[to]) {
			f = 1;
		}
	}
	return f;
}

bool us[MAXN];
void get_sz(int v, int &sz) {
	us[v] = 1;
	sz++;
	for (int to : g[v]) {
		if (!us[to]) {
			get_sz(to, sz);
		}
	}
}

void subtask3() {
	for (int i = 1; i <= n; i++) {
		if (szof(g[i]) > 2) {
			return;
		}
	}
	vector <pii> vec;
	for (int i = 1; i <= n; i++) {
		if (!us[i]) {
			int sz = 0;
			get_sz(i, sz);
			vec.pb({cycle(i), sz});
		}
	}
	
	//cout << "wtf vec: " << endl;
	//for (auto el : vec) {
		//cout << "! " << el.fr << " " << el.sc << endl;
	//}
	
	int ans = 0;
	for (pii el : vec) {
		int cycle = el.fr;
		int sz = el.sc;
		if (sz < 3) {
			continue;
		}
		if (cycle) {
			ans += sz * (sz - 1) * (sz - 2);
		} else {
			int sum = 0;
			for (int i = 1; i <= sz; i++) {
				sum += (i - 1) * (sz - i) * 2;
			}
			ans += sum;
		}
	}
	cout << ans << endl;
	exit(0);
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	// могут быть несколько компонент
	if (n <= 10 && m <= 100) {
		subtask1();
	} else {
		subtask3();		
	}
}
/*
12 2
12 11
9 11
*/

Subtask #1
5.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	2636 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	Correct	2 ms	2636 KB	Output is correct
8	Correct	3 ms	2636 KB	Output is correct
9	Correct	2 ms	2636 KB	Output is correct
10	Correct	2 ms	2636 KB	Output is correct
11	Correct	2 ms	2636 KB	Output is correct
12	Correct	2 ms	2636 KB	Output is correct
13	Correct	2 ms	2636 KB	Output is correct
14	Correct	2 ms	2636 KB	Output is correct
15	Correct	2 ms	2636 KB	Output is correct
16	Correct	2 ms	2636 KB	Output is correct
17	Correct	2 ms	2636 KB	Output is correct
18	Correct	2 ms	2636 KB	Output is correct
19	Correct	2 ms	2636 KB	Output is correct
20	Correct	2 ms	2636 KB	Output is correct
21	Correct	2 ms	2636 KB	Output is correct
22	Correct	2 ms	2636 KB	Output is correct
23	Correct	2 ms	2636 KB	Output is correct
24	Correct	2 ms	2636 KB	Output is correct
25	Correct	2 ms	2636 KB	Output is correct
26	Correct	2 ms	2636 KB	Output is correct
27	Correct	2 ms	2636 KB	Output is correct
28	Correct	2 ms	2636 KB	Output is correct
29	Correct	2 ms	2636 KB	Output is correct
30	Correct	2 ms	2636 KB	Output is correct
31	Correct	2 ms	2636 KB	Output is correct
32	Correct	2 ms	2636 KB	Output is correct
33	Correct	2 ms	2636 KB	Output is correct
34	Correct	2 ms	2636 KB	Output is correct
35	Correct	2 ms	2636 KB	Output is correct

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	2636 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	Correct	2 ms	2636 KB	Output is correct
8	Correct	3 ms	2636 KB	Output is correct
9	Correct	2 ms	2636 KB	Output is correct
10	Correct	2 ms	2636 KB	Output is correct
11	Correct	2 ms	2636 KB	Output is correct
12	Correct	2 ms	2636 KB	Output is correct
13	Correct	2 ms	2636 KB	Output is correct
14	Correct	2 ms	2636 KB	Output is correct
15	Correct	2 ms	2636 KB	Output is correct
16	Correct	2 ms	2636 KB	Output is correct
17	Correct	2 ms	2636 KB	Output is correct
18	Correct	2 ms	2636 KB	Output is correct
19	Correct	2 ms	2636 KB	Output is correct
20	Correct	2 ms	2636 KB	Output is correct
21	Correct	2 ms	2636 KB	Output is correct
22	Correct	2 ms	2636 KB	Output is correct
23	Correct	2 ms	2636 KB	Output is correct
24	Correct	2 ms	2636 KB	Output is correct
25	Correct	2 ms	2636 KB	Output is correct
26	Correct	2 ms	2636 KB	Output is correct
27	Correct	2 ms	2636 KB	Output is correct
28	Correct	2 ms	2636 KB	Output is correct
29	Correct	2 ms	2636 KB	Output is correct
30	Correct	2 ms	2636 KB	Output is correct
31	Correct	2 ms	2636 KB	Output is correct
32	Correct	2 ms	2636 KB	Output is correct
33	Correct	2 ms	2636 KB	Output is correct
34	Correct	2 ms	2636 KB	Output is correct
35	Correct	2 ms	2636 KB	Output is correct
36	Correct	2 ms	2636 KB	Output is correct
37	Incorrect	2 ms	2636 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	12108 KB	Output is correct
2	Correct	127 ms	12304 KB	Output is correct
3	Correct	167 ms	8968 KB	Output is correct
4	Correct	157 ms	11876 KB	Output is correct
5	Correct	130 ms	9284 KB	Output is correct
6	Correct	151 ms	9284 KB	Output is correct
7	Correct	129 ms	8404 KB	Output is correct
8	Correct	129 ms	8900 KB	Output is correct
9	Correct	128 ms	7796 KB	Output is correct
10	Correct	144 ms	8388 KB	Output is correct
11	Correct	99 ms	7584 KB	Output is correct
12	Correct	103 ms	7496 KB	Output is correct
13	Correct	92 ms	7928 KB	Output is correct
14	Correct	81 ms	7756 KB	Output is correct
15	Correct	58 ms	7232 KB	Output is correct
16	Correct	70 ms	7104 KB	Output is correct
17	Correct	5 ms	4944 KB	Output is correct
18	Correct	5 ms	5056 KB	Output is correct
19	Correct	5 ms	5056 KB	Output is correct
20	Correct	5 ms	4928 KB	Output is correct
21	Correct	5 ms	5056 KB	Output is correct
22	Correct	6 ms	5056 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	117 ms	6268 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	94 ms	6268 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	2636 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	Correct	2 ms	2636 KB	Output is correct
8	Correct	3 ms	2636 KB	Output is correct
9	Correct	2 ms	2636 KB	Output is correct
10	Correct	2 ms	2636 KB	Output is correct
11	Correct	2 ms	2636 KB	Output is correct
12	Correct	2 ms	2636 KB	Output is correct
13	Correct	2 ms	2636 KB	Output is correct
14	Correct	2 ms	2636 KB	Output is correct
15	Correct	2 ms	2636 KB	Output is correct
16	Correct	2 ms	2636 KB	Output is correct
17	Correct	2 ms	2636 KB	Output is correct
18	Correct	2 ms	2636 KB	Output is correct
19	Correct	2 ms	2636 KB	Output is correct
20	Correct	2 ms	2636 KB	Output is correct
21	Correct	2 ms	2636 KB	Output is correct
22	Correct	2 ms	2636 KB	Output is correct
23	Correct	2 ms	2636 KB	Output is correct
24	Correct	2 ms	2636 KB	Output is correct
25	Correct	2 ms	2636 KB	Output is correct
26	Correct	2 ms	2636 KB	Output is correct
27	Correct	2 ms	2636 KB	Output is correct
28	Correct	2 ms	2636 KB	Output is correct
29	Correct	2 ms	2636 KB	Output is correct
30	Correct	2 ms	2636 KB	Output is correct
31	Correct	2 ms	2636 KB	Output is correct
32	Correct	2 ms	2636 KB	Output is correct
33	Correct	2 ms	2636 KB	Output is correct
34	Correct	2 ms	2636 KB	Output is correct
35	Correct	2 ms	2636 KB	Output is correct
36	Correct	2 ms	2636 KB	Output is correct
37	Incorrect	2 ms	2636 KB	Output isn't correct
38	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	2636 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	Correct	2 ms	2636 KB	Output is correct
8	Correct	3 ms	2636 KB	Output is correct
9	Correct	2 ms	2636 KB	Output is correct
10	Correct	2 ms	2636 KB	Output is correct
11	Correct	2 ms	2636 KB	Output is correct
12	Correct	2 ms	2636 KB	Output is correct
13	Correct	2 ms	2636 KB	Output is correct
14	Correct	2 ms	2636 KB	Output is correct
15	Correct	2 ms	2636 KB	Output is correct
16	Correct	2 ms	2636 KB	Output is correct
17	Correct	2 ms	2636 KB	Output is correct
18	Correct	2 ms	2636 KB	Output is correct
19	Correct	2 ms	2636 KB	Output is correct
20	Correct	2 ms	2636 KB	Output is correct
21	Correct	2 ms	2636 KB	Output is correct
22	Correct	2 ms	2636 KB	Output is correct
23	Correct	2 ms	2636 KB	Output is correct
24	Correct	2 ms	2636 KB	Output is correct
25	Correct	2 ms	2636 KB	Output is correct
26	Correct	2 ms	2636 KB	Output is correct
27	Correct	2 ms	2636 KB	Output is correct
28	Correct	2 ms	2636 KB	Output is correct
29	Correct	2 ms	2636 KB	Output is correct
30	Correct	2 ms	2636 KB	Output is correct
31	Correct	2 ms	2636 KB	Output is correct
32	Correct	2 ms	2636 KB	Output is correct
33	Correct	2 ms	2636 KB	Output is correct
34	Correct	2 ms	2636 KB	Output is correct
35	Correct	2 ms	2636 KB	Output is correct
36	Correct	2 ms	2636 KB	Output is correct
37	Incorrect	2 ms	2636 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Submission #387817

Compilation message