oj.uz

Submission #252383

# Submission time Handle Problem Language Result Execution time Memory
252383 2020-07-25T12:14:24 Z Saboon Duathlon (APIO18_duathlon) C++14
31 / 100
 114 ms 28920 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 20;
const int mod = 1e9 + 7;

vector<int> g[maxn], t[maxn];
int dw[maxn], h[maxn], rt[maxn], a[maxn], sz[maxn];
bool visited[maxn];
int sz2[maxn];
ll answer = 0;

void dfs2(int v, int par = -1){
	sz2[v] = a[v];
	for (auto u : t[v]){
		if (u != par){
			dfs2(u, v);
			sz2[v] += sz2[u];
			answer += 1ll * sz2[u] * (sz[rt[v]] - sz2[u] - a[v]);
		}
	}
	if (par != -1)
		answer += 1ll * (sz2[v] - a[v]) * (sz[rt[v]] - sz2[v]);
}

int dfs(int v, int root){
	rt[v] = root;
	visited[v] = true;
	int ret = h[v];
	sz[v] = 1;
	dw[v] = v;
	a[v] = 1;
	for (auto u : g[v]){
		if (!visited[u]){
			h[u] = h[v] + 1;
			int k = dfs(u, root);
			sz[v] += sz[u];
			if (k <= h[v]){
				a[v] = a[u];
				dw[v] = dw[u];
			}
			ret = min(ret, k);
		}
		else if (h[u] < h[v] - 1){
			dw[v] = v;
			a[v] = h[v] - h[u] + 1;
			ret = h[u];
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int v = 1; v <= n; v++)
		if (!visited[v])
			dfs(v, v);
	for (int i = 1; i <= n; i++)
		for (auto j : g[i])
			if (dw[i] != dw[j])
				t[dw[i]].push_back(dw[j]);
	memset(visited, 0, sizeof visited);
	for (int v = 1; v <= n; v++)
		if (h[v] == 0)
			dfs2(v);
	for (int v = 1; v <= n; v++)
		if (dw[v] == v and a[v] >= 3)
			answer -= 1ll*a[v]*(a[v]-1)*(a[v]-2);
	for (int f = 1; f <= n; f++){
		if (a[dw[f]] == 1)
			continue;
		int subsz = 1;
		for (auto u : g[f]){
			if (h[u] == h[f]+1 and dw[u] != dw[f])
				subsz += sz[u];
			if (h[u] == h[f]-1 and dw[u] != dw[f])
				subsz += (sz[rt[f]] - sz[f]);
		}
		int outsz = sz[rt[f]] - subsz;
		answer += 2ll*(a[dw[f]]-1) * (outsz-1);
	}
	cout << answer << endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 28920 KB Output is correct
2 Correct 80 ms 28828 KB Output is correct
3 Correct 104 ms 27004 KB Output is correct
4 Correct 83 ms 28152 KB Output is correct
5 Correct 85 ms 25080 KB Output is correct
6 Correct 103 ms 25848 KB Output is correct
7 Correct 103 ms 24868 KB Output is correct
8 Correct 114 ms 25492 KB Output is correct
9 Correct 87 ms 24188 KB Output is correct
10 Correct 98 ms 24568 KB Output is correct
11 Correct 96 ms 22904 KB Output is correct
12 Correct 83 ms 22772 KB Output is correct
13 Correct 64 ms 22776 KB Output is correct
14 Correct 67 ms 22520 KB Output is correct
15 Correct 57 ms 22136 KB Output is correct
16 Correct 58 ms 21880 KB Output is correct
17 Correct 11 ms 17024 KB Output is correct
18 Correct 10 ms 17024 KB Output is correct
19 Correct 10 ms 17024 KB Output is correct
20 Correct 10 ms 17024 KB Output is correct
21 Correct 11 ms 16896 KB Output is correct
22 Correct 10 ms 16896 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 24824 KB Output is correct
2 Correct 89 ms 24824 KB Output is correct
3 Correct 84 ms 24824 KB Output is correct
4 Correct 86 ms 24752 KB Output is correct
5 Correct 86 ms 24824 KB Output is correct
6 Correct 105 ms 28792 KB Output is correct
7 Correct 104 ms 27512 KB Output is correct
8 Correct 94 ms 26744 KB Output is correct
9 Correct 94 ms 25976 KB Output is correct
10 Correct 86 ms 24824 KB Output is correct
11 Correct 87 ms 24824 KB Output is correct
12 Correct 86 ms 24824 KB Output is correct
13 Correct 87 ms 24824 KB Output is correct
14 Correct 81 ms 24568 KB Output is correct
15 Correct 72 ms 24184 KB Output is correct
16 Correct 49 ms 22392 KB Output is correct
17 Correct 62 ms 25440 KB Output is correct
18 Correct 64 ms 25456 KB Output is correct
19 Correct 70 ms 25324 KB Output is correct
20 Correct 63 ms 25336 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14848 KB Output is correct
2 Correct 9 ms 14848 KB Output is correct
3 Incorrect 12 ms 14848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 24824 KB Output is correct
2 Correct 87 ms 24696 KB Output is correct
3 Incorrect 95 ms 23800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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