oj.uz

Submission #217576

# Submission time Handle Problem Language Result Execution time Memory
217576 2020-03-30T09:31:32 Z VEGAnn Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int oo = 2e9;
vector<int> g[N];
int n, m, siz[N], SZ;
bool mrk[N];
ll ans = 0;

void dfs(int v, int p){
    siz[v] = 1;
    mrk[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
        siz[v] += siz[u];
    }
}

void DFS(int v, int p){
    ll sum = 0;

    for (int u : g[v]){
        if (u == p) continue;
        DFS(u, v);

        ans += sum * ll(siz[u]);
        sum += siz[u];
    }

    ans += sum * (ll(SZ) - ll(siz[v]));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

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

    for (int i = 0; i < n; i++)
        if (!mrk[i]){
            dfs(i, -1);
            SZ = siz[i];
            DFS(i, -1);
        }

    cout << ans * 2;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 573 ms 1048580 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 573 ms 1048580 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 1126 ms 491304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7720 KB Output is correct
2 Correct 59 ms 7672 KB Output is correct
3 Correct 56 ms 7672 KB Output is correct
4 Correct 59 ms 7672 KB Output is correct
5 Correct 56 ms 7676 KB Output is correct
6 Correct 74 ms 11768 KB Output is correct
7 Correct 70 ms 10364 KB Output is correct
8 Correct 67 ms 9644 KB Output is correct
9 Correct 66 ms 8952 KB Output is correct
10 Correct 65 ms 7680 KB Output is correct
11 Correct 57 ms 7672 KB Output is correct
12 Correct 58 ms 7684 KB Output is correct
13 Correct 59 ms 7672 KB Output is correct
14 Correct 52 ms 7416 KB Output is correct
15 Correct 45 ms 7160 KB Output is correct
16 Correct 29 ms 6136 KB Output is correct
17 Correct 40 ms 7920 KB Output is correct
18 Correct 43 ms 7920 KB Output is correct
19 Correct 57 ms 7920 KB Output is correct
20 Correct 42 ms 7936 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Runtime error 680 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 62 ms 7672 KB Output is correct
2 Correct 69 ms 7676 KB Output is correct
3 Runtime error 846 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 573 ms 1048580 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 573 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -