oj.uz

Submission #927767

# Submission time Handle Problem Language Result Execution time Memory
927767 2024-02-15T10:10:04 Z TAhmed33 Duathlon (APIO18_duathlon) C++
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector <int> adj[300001];
int sze[300001];
bool vis[300001];
void calc (int pos, int par) {
  	vis[pos] = 1;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		calc(j, pos);
		sze[pos] += sze[j];
	}
	sze[pos]++;
}
int ans = 0;
void dfs (int pos, int par, int l) {
  	vis[pos] = 1;
    ans += 2 * (l - sze[pos]) * (sze[pos] - 1);
    int cur = 0;
    for (auto j : adj[pos]) {
        if (j == par) continue;
        ans += 2 * sze[j] * cur;
        cur += sze[j];
        dfs(j, pos, l);
    }
}
signed main () {
    cin >> n; int m; cin >> m; 
    for (int i = 1; i <= m; i++) {
	    int a, b;
	    cin >> a >> b;
	    adj[a].push_back(b);
	    adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) calc(i, -1);
    memset(vis, 0, sizeof(vis));
  	for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, -1, sze[i]);
  	cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 617 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 617 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13836 KB Output is correct
2 Correct 57 ms 13664 KB Output is correct
3 Correct 57 ms 13652 KB Output is correct
4 Correct 56 ms 13648 KB Output is correct
5 Correct 58 ms 13652 KB Output is correct
6 Correct 63 ms 17388 KB Output is correct
7 Correct 62 ms 16468 KB Output is correct
8 Correct 61 ms 15760 KB Output is correct
9 Correct 62 ms 15152 KB Output is correct
10 Correct 57 ms 13724 KB Output is correct
11 Correct 57 ms 14932 KB Output is correct
12 Correct 59 ms 14932 KB Output is correct
13 Correct 71 ms 15052 KB Output is correct
14 Correct 57 ms 14652 KB Output is correct
15 Correct 47 ms 14164 KB Output is correct
16 Correct 32 ms 13148 KB Output is correct
17 Correct 50 ms 15280 KB Output is correct
18 Correct 50 ms 15172 KB Output is correct
19 Correct 54 ms 15200 KB Output is correct
20 Correct 55 ms 15196 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Runtime error 656 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13652 KB Output is correct
2 Correct 65 ms 13652 KB Output is correct
3 Runtime error 740 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 617 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 617 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -