oj.uz

Submission #59307

# Submission time Handle Problem Language Result Execution time Memory
59307 2018-07-21T13:08:55 Z thiago4532 Duathlon (APIO18_duathlon) C++17
10 / 100
 140 ms 12920 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, inf = 0x3f3f3f3f;
vector<int> grafo[maxn];
int sz[maxn];
int mark[maxn];
bool test[maxn];

void dfs(int u, int p=0){
	if(mark[u]) return;
	mark[u] = true;

	sz[u] = 1;
	for(auto v : grafo[u]){
		if(v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

int ans;
void solve(int u, int p=0, int acc=0){
	if(test[u]) return;
	test[u] = true;

	ans += (2 * acc * (sz[u] - 1));

	for(auto v : grafo[u]){
		if(v == p) continue;
		ans += (sz[u] - sz[v] - 1) * sz[v];
		solve(v, u, sz[u] - sz[v] + acc);
	}
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}

	for(int i=1;i<=n;i++)
		dfs(i);

	for(int i=1;i<=n;i++)
		solve(i);

	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 12920 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 6 ms 12920 KB Output is correct
2 Correct 6 ms 12920 KB Output is correct
3 Correct 5 ms 12920 KB Output is correct
4 Correct 5 ms 12920 KB Output is correct
5 Correct 7 ms 12920 KB Output is correct
6 Correct 6 ms 12920 KB Output is correct
7 Correct 5 ms 12920 KB Output is correct
8 Correct 4 ms 12920 KB Output is correct
9 Correct 4 ms 12920 KB Output is correct
10 Correct 4 ms 12920 KB Output is correct
11 Correct 5 ms 12920 KB Output is correct
12 Correct 4 ms 12920 KB Output is correct
13 Correct 6 ms 12920 KB Output is correct
14 Correct 7 ms 12920 KB Output is correct
15 Correct 6 ms 12920 KB Output is correct
16 Correct 6 ms 12920 KB Output is correct
17 Correct 5 ms 12920 KB Output is correct
18 Correct 5 ms 12920 KB Output is correct
19 Correct 5 ms 12920 KB Output is correct
20 Correct 5 ms 12920 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12920 KB Output is correct
2 Correct 5 ms 12920 KB Output is correct
3 Incorrect 7 ms 12920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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