oj.uz

Submission #59299

# Submission time Handle Problem Language Result Execution time Memory
59299 2018-07-21T12:36:33 Z MatheusLealV Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 919288 KB 
#include <bits/stdc++.h>
#define N 100050
using namespace std;
typedef long long ll;

ll n, m, ok[N], ans, sz[N];

vector<int> grafo[N];

ll tot;

void fill(int x, int p)
{
	tot ++;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		fill(v, x);
	}
}

void dfs(int x, int p)
{	
	sz[x] = ok[x] = 1;

	ll quadrado = 0, soma = 0;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		dfs(v, x);

		quadrado += sz[v] * sz[v];

		soma += sz[v];

		sz[x] += sz[v];
	}

	soma += tot - sz[x];

	quadrado += (tot - sz[x]) * (tot - sz[x]);

	ll prod2 = (soma * soma - quadrado);

	ans += prod2;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1, a, b; i <= m; i++)
	{
		cin>>a>>b;

		grafo[a].push_back(b);

		grafo[b].push_back(a);
	}

	for(int i = 1; i <= n; i++)
	{
		if(ok[i]) continue;

		tot = 0;

		fill(i, i);

		dfs(i, i);
	}

	cout<<ans<<"\n";

	//cout<<brute()<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 645656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 645656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 645656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 645656 KB Output is correct
2 Correct 100 ms 645656 KB Output is correct
3 Correct 123 ms 645656 KB Output is correct
4 Correct 132 ms 645656 KB Output is correct
5 Correct 161 ms 645656 KB Output is correct
6 Correct 138 ms 645656 KB Output is correct
7 Correct 123 ms 645656 KB Output is correct
8 Correct 130 ms 645656 KB Output is correct
9 Correct 129 ms 645656 KB Output is correct
10 Correct 138 ms 645656 KB Output is correct
11 Correct 148 ms 645656 KB Output is correct
12 Correct 91 ms 645656 KB Output is correct
13 Correct 128 ms 645656 KB Output is correct
14 Correct 119 ms 645656 KB Output is correct
15 Correct 70 ms 645656 KB Output is correct
16 Correct 71 ms 645656 KB Output is correct
17 Correct 63 ms 645656 KB Output is correct
18 Correct 55 ms 645656 KB Output is correct
19 Correct 70 ms 645656 KB Output is correct
20 Correct 77 ms 645656 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 645656 KB Output is correct
2 Correct 5 ms 645656 KB Output is correct
3 Execution timed out 1130 ms 833784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 833784 KB Output is correct
2 Correct 91 ms 833784 KB Output is correct
3 Execution timed out 1124 ms 919288 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 645656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 645656 KB Time limit exceeded
2 Halted 0 ms 0 KB -