oj.uz

Submission #710245

# Submission time Handle Problem Language Result Execution time Memory
710245 2023-03-15T06:03:16 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 87 ms 15632 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], g[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];
    }
}

bool F;
int ct;

void dfs_check(int u, int par, bool g[]){
    ++ct;
    g[u] = true;
    for(int i : a[u]){
        if (i == par) continue;
        if (g[i]){
            F = false;
            continue;
        }

        dfs_check(i, u, g);
    }
}

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]){
            F = true; ct = 0;
            dfs_check(i, 0, g);

            if (F){
                dfs_precal(i);
                dfs(i, i);
            } else {
                ans += ct * (ct - 1) * (ct - 2);
                dfs_check(i, 0, f);
            }
        }
    }

    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 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 15320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11980 KB Output is correct
2 Correct 55 ms 12088 KB Output is correct
3 Correct 58 ms 12040 KB Output is correct
4 Correct 61 ms 12088 KB Output is correct
5 Correct 61 ms 11972 KB Output is correct
6 Correct 67 ms 15632 KB Output is correct
7 Correct 87 ms 14856 KB Output is correct
8 Correct 71 ms 14100 KB Output is correct
9 Correct 60 ms 13344 KB Output is correct
10 Correct 54 ms 11984 KB Output is correct
11 Correct 58 ms 12044 KB Output is correct
12 Correct 59 ms 11976 KB Output is correct
13 Correct 46 ms 12092 KB Output is correct
14 Correct 46 ms 11872 KB Output is correct
15 Correct 44 ms 11588 KB Output is correct
16 Correct 23 ms 10760 KB Output is correct
17 Correct 30 ms 12164 KB Output is correct
18 Correct 32 ms 12224 KB Output is correct
19 Correct 30 ms 12284 KB Output is correct
20 Correct 31 ms 12276 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Incorrect 5 ms 7380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11984 KB Output is correct
2 Correct 58 ms 11932 KB Output is correct
3 Incorrect 59 ms 11556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -