oj.uz

Submission #387831

# Submission time Handle Problem Language Result Execution time Memory
387831 2021-04-09T09:04:47 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
36 / 100
 835 ms 1048580 KB 
#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});
		}
	}
	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);
}


int sub[MAXN];
void precalc(int v, int par) {
	sub[v] = 1;
	used[v] = 1;
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		precalc(to, v);
		sub[v] += sub[to];
	}
}

int tree_ans = 0;
void calc(int v, int par, int root) {
	vector <int> vec;
	for (int to : g[v]) {
		if (to != par) {
			calc(to, v, root);
			vec.pb(sub[to]);
		}
	}
	int sum = 0;
	vec.pb(sub[root] - sub[v]);
	int before = 0;
	for (int i = 0; i < szof(vec); i++) {
		sum += vec[i] * before;
		before += vec[i];
	}
	tree_ans += sum * 2;
}

void solve_for_tree() {
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			precalc(i, -1);
			calc(i, -1, i);
		}
	}
	cout << tree_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();
	}
	subtask3();
	solve_for_tree();
}
/*
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 2644 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 2640 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 2 ms 2572 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 2644 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 2640 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 2 ms 2572 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 Correct 2 ms 2636 KB Output is correct
38 Runtime error 550 ms 1048580 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 12180 KB Output is correct
2 Correct 125 ms 12216 KB Output is correct
3 Correct 122 ms 9116 KB Output is correct
4 Correct 116 ms 10656 KB Output is correct
5 Correct 112 ms 8048 KB Output is correct
6 Correct 112 ms 7984 KB Output is correct
7 Correct 110 ms 7108 KB Output is correct
8 Correct 113 ms 7652 KB Output is correct
9 Correct 104 ms 6548 KB Output is correct
10 Correct 104 ms 7108 KB Output is correct
11 Correct 86 ms 6472 KB Output is correct
12 Correct 82 ms 6480 KB Output is correct
13 Correct 82 ms 6872 KB Output is correct
14 Correct 74 ms 6848 KB Output is correct
15 Correct 59 ms 6516 KB Output is correct
16 Correct 57 ms 6336 KB Output is correct
17 Correct 5 ms 5056 KB Output is correct
18 Correct 6 ms 5056 KB Output is correct
19 Correct 5 ms 4928 KB Output is correct
20 Correct 5 ms 4928 KB Output is correct
21 Correct 5 ms 4928 KB Output is correct
22 Correct 5 ms 5056 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2664 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2656 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2656 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 3 ms 2636 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7236 KB Output is correct
2 Correct 116 ms 8516 KB Output is correct
3 Correct 127 ms 8492 KB Output is correct
4 Correct 120 ms 8508 KB Output is correct
5 Correct 122 ms 8496 KB Output is correct
6 Correct 116 ms 10596 KB Output is correct
7 Correct 137 ms 12460 KB Output is correct
8 Correct 142 ms 11420 KB Output is correct
9 Correct 130 ms 10428 KB Output is correct
10 Correct 122 ms 8496 KB Output is correct
11 Correct 121 ms 8600 KB Output is correct
12 Correct 116 ms 8512 KB Output is correct
13 Correct 120 ms 8388 KB Output is correct
14 Correct 98 ms 8132 KB Output is correct
15 Correct 91 ms 7828 KB Output is correct
16 Correct 57 ms 6468 KB Output is correct
17 Correct 95 ms 10176 KB Output is correct
18 Correct 93 ms 9828 KB Output is correct
19 Correct 89 ms 9820 KB Output is correct
20 Correct 93 ms 9500 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Runtime error 662 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7236 KB Output is correct
2 Correct 126 ms 8276 KB Output is correct
3 Runtime error 835 ms 1048580 KB Execution killed with signal 9
4 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 2644 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 2640 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 2 ms 2572 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 Correct 2 ms 2636 KB Output is correct
38 Runtime error 550 ms 1048580 KB Execution killed with signal 9
39 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 2644 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 2640 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 2 ms 2572 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 Correct 2 ms 2636 KB Output is correct
38 Runtime error 550 ms 1048580 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -