oj.uz

Submission #725012

# Submission time Handle Problem Language Result Execution time Memory
725012 2023-04-16T12:56:40 Z Sohsoh84 Duathlon (APIO18_duathlon) C++17
23 / 100
 125 ms 66756 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;

int n, m, H[MAXN], tin[MAXN], low[MAXN], t, cnt, sz[MAXN];
stack<int> st;
vector<int> adj[MAXN], G[MAXN];
bool vis[MAXN];
ll ans = 0;

void dfs(int v, int p) {
	st.push(v);
	tin[v] = low[v] = t++;
	for (int u : adj[v]) {
		if (u == p) continue;
		if (tin[u]) low[v] = min(low[v], tin[u]);
		else {
			dfs(u, v);
			low[v] = min(low[v], low[u]);
			if (low[u] >= tin[v]) {
				cnt++;
				G[v].push_back(n + cnt);
				while (G[n + cnt].empty() || G[n + cnt].back() != u) {
					G[n + cnt].push_back(st.top());
					st.pop();
				}
			}
		}
	}
}

void solve(int v) {
	if (v <= n) sz[v] = 1;
	for (int u : G[v]) {
		solve(u);
		sz[v] += sz[u];
		if (v > n) ans -= 1ll * sz[u] * (sz[u] - 1) * G[v].size();
	}

	if (v > n) ans -= 1ll * (t - sz[v]) * (t - sz[v] - 1) * G[v].size();
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		if (tin[i]) continue;
		t = 0;
		dfs(i, 0);

		ans += 1ll * t * (t - 1) * (t - 2);
		solve(i);
	}

	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 24 ms 47304 KB Output is correct
3 Correct 24 ms 47324 KB Output is correct
4 Correct 24 ms 47436 KB Output is correct
5 Correct 23 ms 47452 KB Output is correct
6 Correct 26 ms 47428 KB Output is correct
7 Correct 24 ms 47508 KB Output is correct
8 Correct 27 ms 47444 KB Output is correct
9 Correct 22 ms 47468 KB Output is correct
10 Correct 24 ms 47300 KB Output is correct
11 Correct 31 ms 47408 KB Output is correct
12 Correct 25 ms 47420 KB Output is correct
13 Correct 29 ms 47412 KB Output is correct
14 Correct 23 ms 47404 KB Output is correct
15 Correct 26 ms 47384 KB Output is correct
16 Correct 23 ms 47260 KB Output is correct
17 Correct 24 ms 47444 KB Output is correct
18 Correct 22 ms 47312 KB Output is correct
19 Correct 23 ms 47400 KB Output is correct
20 Correct 29 ms 47316 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 56860 KB Output is correct
2 Correct 99 ms 56768 KB Output is correct
3 Correct 89 ms 56788 KB Output is correct
4 Correct 86 ms 56804 KB Output is correct
5 Correct 119 ms 56808 KB Output is correct
6 Correct 115 ms 66756 KB Output is correct
7 Correct 98 ms 63140 KB Output is correct
8 Correct 101 ms 61552 KB Output is correct
9 Correct 108 ms 60000 KB Output is correct
10 Correct 125 ms 56824 KB Output is correct
11 Correct 106 ms 58020 KB Output is correct
12 Correct 89 ms 58068 KB Output is correct
13 Correct 94 ms 58124 KB Output is correct
14 Correct 105 ms 57500 KB Output is correct
15 Correct 112 ms 57040 KB Output is correct
16 Correct 56 ms 54596 KB Output is correct
17 Correct 66 ms 57192 KB Output is correct
18 Correct 62 ms 57156 KB Output is correct
19 Correct 77 ms 57228 KB Output is correct
20 Correct 98 ms 57152 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47404 KB Output is correct
2 Correct 23 ms 47356 KB Output is correct
3 Correct 23 ms 47400 KB Output is correct
4 Incorrect 23 ms 47276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 56808 KB Output is correct
2 Correct 120 ms 57128 KB Output is correct
3 Correct 124 ms 56304 KB Output is correct
4 Incorrect 89 ms 54524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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