oj.uz

Submission #374710

# Submission time Handle Problem Language Result Execution time Memory
374710 2021-03-08T01:00:42 Z morato Duathlon (APIO18_duathlon) C++17
0 / 100
 116 ms 27244 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

long long ans;
int n, m, tt, cnt_bcc, tam;
int tin[maxn], low[maxn], subtree[2 * maxn];

vector<int> adj[maxn], bcc[2 * maxn];

stack<int> stk;

void dfs(int on, int par = -1) {
	tin[on] = low[on] = ++tt;
	stk.push(on);
	tam++;
	for (int to : adj[on]) if (to != par) {
		if (tin[to]) {
			low[on] = min(low[on], tin[to]);
		} else {
			dfs(to, on);
			low[on] = min(low[on], low[to]);
			if (low[to] >= tin[on]) {
				cnt_bcc++;
				bcc[on].push_back(n + cnt_bcc);
				while (bcc[n + cnt_bcc].empty() || bcc[n + cnt_bcc].back() != to) {
					bcc[n + cnt_bcc].push_back(stk.top());
					stk.pop();
				}
			}
		}
	}
}

void dfs2(int on) {
	subtree[on] = (on <= n);
	for (int to : bcc[on]) {
		dfs2(to); // escolhendo o par (x, y) em cada ponto da minha subtree
		subtree[on] += subtree[to];
		if (on > n) ans -= 1ll * ((int) bcc[on].size()) * subtree[to] * (subtree[to] - 1);
	}
	// escolhendo o par (x, y) fora da minha subtree
	if (on > n) ans -= 1ll * ((int) bcc[on].size()) * (tam - subtree[on]) * (tam - subtree[on] - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
    	int a, b;
    	cin >> a >> b;
    	adj[a].push_back(b);
    	adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
    	if (!tin[i]) {
    		tam = 0;
    		dfs(i);
    		ans += 1ll * n * (n - 1) * (n - 2);
    		dfs2(i);
    	}
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 24168 KB Output is correct
2 Correct 87 ms 23912 KB Output is correct
3 Incorrect 99 ms 22000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17644 KB Output is correct
2 Correct 94 ms 17388 KB Output is correct
3 Correct 101 ms 17260 KB Output is correct
4 Correct 100 ms 17260 KB Output is correct
5 Correct 102 ms 17236 KB Output is correct
6 Correct 116 ms 27244 KB Output is correct
7 Correct 108 ms 23612 KB Output is correct
8 Correct 106 ms 21996 KB Output is correct
9 Correct 106 ms 20624 KB Output is correct
10 Incorrect 105 ms 17376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7532 KB Output is correct
2 Correct 6 ms 7532 KB Output is correct
3 Correct 6 ms 7532 KB Output is correct
4 Correct 6 ms 7532 KB Output is correct
5 Correct 7 ms 7532 KB Output is correct
6 Correct 6 ms 7532 KB Output is correct
7 Correct 6 ms 7532 KB Output is correct
8 Correct 6 ms 7532 KB Output is correct
9 Correct 6 ms 7532 KB Output is correct
10 Correct 6 ms 7532 KB Output is correct
11 Correct 6 ms 7532 KB Output is correct
12 Correct 7 ms 7532 KB Output is correct
13 Correct 6 ms 7660 KB Output is correct
14 Correct 6 ms 7532 KB Output is correct
15 Correct 6 ms 7532 KB Output is correct
16 Incorrect 6 ms 7532 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 17644 KB Output is correct
2 Correct 98 ms 17644 KB Output is correct
3 Correct 105 ms 16748 KB Output is correct
4 Correct 100 ms 16748 KB Output is correct
5 Correct 96 ms 15560 KB Output is correct
6 Correct 87 ms 15084 KB Output is correct
7 Correct 82 ms 14572 KB Output is correct
8 Correct 79 ms 14188 KB Output is correct
9 Correct 79 ms 14060 KB Output is correct
10 Correct 76 ms 14060 KB Output is correct
11 Correct 72 ms 13804 KB Output is correct
12 Correct 71 ms 13900 KB Output is correct
13 Correct 80 ms 13932 KB Output is correct
14 Correct 75 ms 16512 KB Output is correct
15 Correct 114 ms 24172 KB Output is correct
16 Correct 114 ms 22124 KB Output is correct
17 Correct 116 ms 22636 KB Output is correct
18 Correct 113 ms 20716 KB Output is correct
19 Incorrect 99 ms 16748 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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