oj.uz

Submission #59301

# Submission time Handle Problem Language Result Execution time Memory
59301 2018-07-21T12:55:47 Z thiago4532 Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 1049600 KB 
#include <bits/stdc++.h>

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

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

		mark[v] = mark[u];	
		dfs(v, u);
		sz[u] += sz[v];
	}

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

int ans=0;
void rotate(int u, int p=0){
	ans += calc[u];
	for(auto v : grafo[u]){
		if(v == p) continue;

		int x = calc[u], y = sz[u], z = calc[v], k = sz[v];;
		calc[u] -= ((sz[u] - sz[v] - 1) * sz[v]) * (grafo[u].size());
		
		sz[u] -= sz[v];
		sz[v] += sz[u];

		calc[v] = 0;
		for(auto l : grafo[v]){
			calc[v] += (sz[v] - sz[l] - 1) * sz[l];
		}
		calc[u] = x, sz[u] = y, calc[v] = z, sz[v] = k;
	}
}

int main(){
	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);
	}

	int cnt=0;
	for(int i=1;i<=n;i++)
		if(!mark[i]) mark[i] = ++cnt, root[cnt] = i, dfs(i);

	for(int i=1;i<=cnt;i++){
		rotate(root[i]);
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1140 ms 1049600 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 1140 ms 1049600 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 1077 ms 1049600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1140 ms 1049600 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 1140 ms 1049600 KB Time limit exceeded
2 Halted 0 ms 0 KB -