oj.uz

Submission #59308

# Submission time Handle Problem Language Result Execution time Memory
59308 2018-07-21T13:10:24 Z thiago4532 Duathlon (APIO18_duathlon) C++17
23 / 100
 164 ms 17472 KB 
#include <bits/stdc++.h>
#define int long long

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);
	}
}

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;
}

Compilation message

count_triplets.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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 143 ms 12240 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 5 ms 12240 KB Output is correct
2 Correct 6 ms 12240 KB Output is correct
3 Correct 5 ms 12240 KB Output is correct
4 Correct 5 ms 12240 KB Output is correct
5 Correct 6 ms 12240 KB Output is correct
6 Correct 7 ms 12240 KB Output is correct
7 Correct 6 ms 12240 KB Output is correct
8 Correct 6 ms 12240 KB Output is correct
9 Correct 5 ms 12240 KB Output is correct
10 Correct 6 ms 12240 KB Output is correct
11 Correct 6 ms 12240 KB Output is correct
12 Correct 5 ms 12240 KB Output is correct
13 Correct 5 ms 12240 KB Output is correct
14 Correct 5 ms 12240 KB Output is correct
15 Correct 6 ms 12240 KB Output is correct
16 Correct 4 ms 12240 KB Output is correct
17 Correct 4 ms 12240 KB Output is correct
18 Correct 5 ms 12240 KB Output is correct
19 Correct 6 ms 12240 KB Output is correct
20 Correct 5 ms 12240 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 12240 KB Output is correct
2 Correct 87 ms 12240 KB Output is correct
3 Correct 118 ms 12240 KB Output is correct
4 Correct 86 ms 12240 KB Output is correct
5 Correct 80 ms 13344 KB Output is correct
6 Correct 154 ms 16712 KB Output is correct
7 Correct 99 ms 17396 KB Output is correct
8 Correct 85 ms 17472 KB Output is correct
9 Correct 138 ms 17472 KB Output is correct
10 Correct 114 ms 17472 KB Output is correct
11 Correct 80 ms 17472 KB Output is correct
12 Correct 86 ms 17472 KB Output is correct
13 Correct 69 ms 17472 KB Output is correct
14 Correct 67 ms 17472 KB Output is correct
15 Correct 53 ms 17472 KB Output is correct
16 Correct 37 ms 17472 KB Output is correct
17 Correct 53 ms 17472 KB Output is correct
18 Correct 48 ms 17472 KB Output is correct
19 Correct 71 ms 17472 KB Output is correct
20 Correct 82 ms 17472 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 17472 KB Output is correct
2 Correct 127 ms 17472 KB Output is correct
3 Incorrect 164 ms 17472 KB Output isn't correct
4 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 -