oj.uz

Submission #124967

# Submission time Handle Problem Language Result Execution time Memory
124967 2019-07-04T08:31:50 Z elabensaad Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;

long long n, m, x, y, vis[300000], ans;
vector <int> t[300000];

void DFS (int v){
	vis[v] = 1;
	for (auto i : t[v]){
		if (vis[i] == 0){DFS(i);vis[v] += vis[i];
		}
	}
}
void dfs (int v, int r, int p = 0){
	ans+=(vis[r]-vis[v])*(vis[v]-1)*2;
	for (auto i : t[v]){
		if (i != p){dfs(i, r, v);ans+=(vis[v]-vis[i]-1)*vis[i];}
	}
}

main() {
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		cin >> x >> y;
		x--;
		y--;
		t[x].push_back(y);
		t[y].push_back(x);	
	}
	for (int i = 0; i < n; i++){
		if (vis[i] == 0){
			DFS(i);		
			dfs(i, i);
		}
	}
	cout << ans;
}

Compilation message

count_triplets.cpp:22: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 Execution timed out 1002 ms 1048580 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 1002 ms 1048580 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 1105 ms 399608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 12664 KB Output is correct
2 Correct 161 ms 12664 KB Output is correct
3 Correct 169 ms 12792 KB Output is correct
4 Correct 158 ms 12664 KB Output is correct
5 Correct 153 ms 12664 KB Output is correct
6 Correct 170 ms 16760 KB Output is correct
7 Correct 171 ms 15384 KB Output is correct
8 Correct 172 ms 14716 KB Output is correct
9 Correct 172 ms 13944 KB Output is correct
10 Correct 168 ms 12636 KB Output is correct
11 Correct 161 ms 12572 KB Output is correct
12 Correct 162 ms 12664 KB Output is correct
13 Correct 163 ms 12628 KB Output is correct
14 Correct 146 ms 12460 KB Output is correct
15 Correct 133 ms 12144 KB Output is correct
16 Correct 86 ms 11128 KB Output is correct
17 Correct 137 ms 12884 KB Output is correct
18 Correct 136 ms 12912 KB Output is correct
19 Correct 136 ms 13032 KB Output is correct
20 Correct 135 ms 12864 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Runtime error 971 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 158 ms 12640 KB Output is correct
2 Correct 171 ms 12564 KB Output is correct
3 Execution timed out 1146 ms 965600 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 1002 ms 1048580 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 1002 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -