oj.uz

Submission #216358

# Submission time Handle Problem Language Result Execution time Memory
216358 2020-03-27T08:06:49 Z theStaticMind Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[300005];
vector<int> sub(300005, 0);
vector<bool> vis(300005, false);
int ans = 0;

void dfs(int x, int pre){
	sub[x] = 1;
	for(auto y : adj[x]){
		if(y == pre) continue;
		dfs(y, x);
		sub[x] += sub[y];
	}
}

void calc(int x, int pre, int sum){
	ans += 2ll * (sub[x] - 1) * (sum - sub[x]);

	int w = 0;

	for(auto y : adj[x]){
		if(y == pre) continue;
		ans += 2ll * sub[y] * w;
		w += sub[y];
	}

	for(auto y : adj[x]){
		if(y == pre) continue;
		calc(y, x, sum);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	vector<int> root;
	for(int i = 1; i <= n; i++){
		if(sub[i] == 0) dfs(i, -1), root.pb(i);
	}
	for(auto r : root) calc(r, -1, sub[r]);

	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13436 KB Output is correct
2 Correct 68 ms 13560 KB Output is correct
3 Correct 80 ms 13432 KB Output is correct
4 Correct 65 ms 13564 KB Output is correct
5 Correct 63 ms 13560 KB Output is correct
6 Correct 76 ms 16248 KB Output is correct
7 Correct 77 ms 15736 KB Output is correct
8 Correct 74 ms 15096 KB Output is correct
9 Correct 73 ms 14584 KB Output is correct
10 Correct 69 ms 13560 KB Output is correct
11 Correct 66 ms 14712 KB Output is correct
12 Correct 67 ms 14712 KB Output is correct
13 Correct 67 ms 14712 KB Output is correct
14 Correct 63 ms 14584 KB Output is correct
15 Correct 56 ms 14456 KB Output is correct
16 Correct 38 ms 13436 KB Output is correct
17 Correct 48 ms 14956 KB Output is correct
18 Correct 49 ms 14952 KB Output is correct
19 Correct 47 ms 15216 KB Output is correct
20 Correct 47 ms 14952 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9776 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Runtime error 648 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13560 KB Output is correct
2 Correct 70 ms 13432 KB Output is correct
3 Runtime error 780 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -