oj.uz

Submission #710220

# Submission time Handle Problem Language Result Execution time Memory
710220 2023-03-15T05:49:08 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 110 ms 15812 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);

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 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 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 15348 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 4 ms 7380 KB Output is correct
3 Correct 5 ms 7376 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7376 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 6 ms 7372 KB Output is correct
11 Correct 5 ms 7356 KB Output is correct
12 Correct 5 ms 7380 KB Output is correct
13 Correct 6 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct
16 Correct 5 ms 7376 KB Output is correct
17 Correct 6 ms 7380 KB Output is correct
18 Correct 5 ms 7356 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 5 ms 7380 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 12060 KB Output is correct
2 Correct 82 ms 12168 KB Output is correct
3 Correct 67 ms 12056 KB Output is correct
4 Correct 76 ms 12164 KB Output is correct
5 Correct 62 ms 12048 KB Output is correct
6 Correct 97 ms 15812 KB Output is correct
7 Correct 110 ms 14924 KB Output is correct
8 Correct 83 ms 14188 KB Output is correct
9 Correct 101 ms 13452 KB Output is correct
10 Correct 81 ms 12108 KB Output is correct
11 Correct 63 ms 13364 KB Output is correct
12 Correct 57 ms 13332 KB Output is correct
13 Correct 77 ms 13304 KB Output is correct
14 Correct 51 ms 12992 KB Output is correct
15 Correct 50 ms 12624 KB Output is correct
16 Correct 39 ms 11384 KB Output is correct
17 Correct 48 ms 13472 KB Output is correct
18 Correct 58 ms 13412 KB Output is correct
19 Correct 71 ms 13388 KB Output is correct
20 Correct 34 ms 13500 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 7380 KB Output is correct
3 Incorrect 7 ms 7376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 12088 KB Output is correct
2 Correct 98 ms 11916 KB Output is correct
3 Incorrect 83 ms 13084 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 7252 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 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -