oj.uz

Submission #710190

# Submission time Handle Problem Language Result Execution time Memory
710190 2023-03-15T05:37:16 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>
#define endl '\n'

#define int long long

using namespace std;

const int N = 3e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

vector <int> a[N];
int sub[N]; bool f[N];
int ans = 0, n;

void dfs(int root, int u, int par = 0){
    f[u] = true;
    int sum = 0;
    for(int i : a[u]){
        if (i == par) continue;
        dfs(root, i, u);

        ans += sum * sub[i];
        sum += sub[i];
    }
    ans += (sub[root] - sub[u]) * (sub[u] - 1);
}

void dfs_precal(int u, int par = 0){
    sub[u] = 1;
    for(int i : a[u]){
        if (i == par) continue;
        dfs_precal(i, u);

        sub[u] += sub[i];
    }
}

void solve()
{
    int m; cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for(int i = 1; i <= n; ++i){
        if (!f[i]){
            dfs_precal(i);
            dfs(i, i);
        }
    }

    cout << 2ll * ans;
}

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

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; // cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 5.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7384 KB Output is correct
5 Correct 4 ms 7368 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 6 ms 7364 KB Output is correct
8 Correct 5 ms 7332 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 4 ms 7392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7376 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7384 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7376 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11924 KB Output is correct
2 Correct 59 ms 12016 KB Output is correct
3 Correct 50 ms 11972 KB Output is correct
4 Correct 56 ms 12052 KB Output is correct
5 Correct 77 ms 11980 KB Output is correct
6 Correct 76 ms 15652 KB Output is correct
7 Correct 70 ms 14808 KB Output is correct
8 Correct 105 ms 14088 KB Output is correct
9 Correct 100 ms 13368 KB Output is correct
10 Correct 50 ms 11996 KB Output is correct
11 Correct 52 ms 13128 KB Output is correct
12 Correct 54 ms 13132 KB Output is correct
13 Correct 73 ms 13132 KB Output is correct
14 Correct 39 ms 12860 KB Output is correct
15 Correct 37 ms 12492 KB Output is correct
16 Correct 24 ms 11220 KB Output is correct
17 Correct 31 ms 13368 KB Output is correct
18 Correct 32 ms 13384 KB Output is correct
19 Correct 33 ms 13376 KB Output is correct
20 Correct 33 ms 13316 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Runtime error 548 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 53 ms 11984 KB Output is correct
2 Correct 65 ms 11764 KB Output is correct
3 Runtime error 655 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 672 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 672 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -