oj.uz

Submission #931604

# Submission time Handle Problem Language Result Execution time Memory
931604 2024-02-22T06:45:45 Z 12345678 Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, m, u, v, vs[nx], sz[nx], res;
vector<int> d[nx];

void dfs(int u, int p)
{
    vs[u]=1;
    ll vl=0, sm=0;
    sz[u]=1;
    for (auto v:d[u]) if (v!=p) dfs(v, u), vl+=(sz[v]), sm+=(sz[v]*sz[v]), sz[u]+=sz[v];
    res+=(vl*vl-sm)/2;
}

void dfs2(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p) res+=(rtsz-sz[v])*(sz[v]-1), dfs2(v, u, rtsz);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=0; i<m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    dfs(1, 1);
    dfs2(1, 1, sz[1]);
    //for (int i=1; i<=n; i++) if (!vs[i]) dfs(i, i), dfs2(i, i, sz[i]);
    cout<<2*res;
}

Subtask #1
0 / 5.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Incorrect 1 ms 2652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7516 KB Output is correct
2 Correct 27 ms 7512 KB Output is correct
3 Correct 27 ms 7508 KB Output is correct
4 Correct 32 ms 7516 KB Output is correct
5 Correct 26 ms 7508 KB Output is correct
6 Correct 39 ms 12372 KB Output is correct
7 Correct 32 ms 10660 KB Output is correct
8 Correct 34 ms 9820 KB Output is correct
9 Correct 33 ms 9052 KB Output is correct
10 Incorrect 26 ms 7508 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 607 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 30 ms 7508 KB Output is correct
2 Correct 28 ms 7512 KB Output is correct
3 Runtime error 676 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 553 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 553 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -