oj.uz

Submission #370667

# Submission time Handle Problem Language Result Execution time Memory
370667 2021-02-24T12:59:48 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> pii;
#define f first
#define s second
const int maxn = 1e5+10;
vector<int> grafo[maxn];
int n, m, dp[maxn], sz[maxn], qtd2[maxn];
int solve(int u, int p = 0){ // lca of path is u, 1 as a root
    int ans = 0; // sum of dps
    sz[u] = 1;
    for(int v : grafo[u]){
        if(v == p) continue;
        ans += solve(v, u);
        sz[u] += sz[v];
        qtd2[u] += qtd2[v] + sz[v];
    }
    int qtd = sz[u] - 1;
    for(int v : grafo[u]){
        if(v == p) continue;
        qtd -= sz[v];
        dp[u] += sz[v] * qtd;
        dp[u] += (sz[u]  - sz[v]) * qtd2[v];
    }
    return ans + dp[u];
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(!sz[i]) ans += solve(i);
    }
    cout << 2*ans << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 570 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 570 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 1120 ms 415416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8812 KB Output is correct
2 Correct 67 ms 8812 KB Output is correct
3 Correct 65 ms 8812 KB Output is correct
4 Correct 72 ms 8812 KB Output is correct
5 Correct 63 ms 8812 KB Output is correct
6 Correct 75 ms 12524 KB Output is correct
7 Correct 81 ms 11500 KB Output is correct
8 Correct 82 ms 10860 KB Output is correct
9 Correct 70 ms 10092 KB Output is correct
10 Correct 66 ms 8940 KB Output is correct
11 Correct 70 ms 9964 KB Output is correct
12 Correct 64 ms 9964 KB Output is correct
13 Correct 64 ms 9964 KB Output is correct
14 Correct 59 ms 9708 KB Output is correct
15 Correct 57 ms 9324 KB Output is correct
16 Correct 34 ms 8172 KB Output is correct
17 Correct 40 ms 8672 KB Output is correct
18 Correct 39 ms 8668 KB Output is correct
19 Correct 38 ms 8792 KB Output is correct
20 Correct 41 ms 8668 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Runtime error 731 ms 1048580 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 69 ms 8940 KB Output is correct
2 Correct 65 ms 8812 KB Output is correct
3 Runtime error 882 ms 1048580 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 570 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 570 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -