Submission #710225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
710225	2023-03-15T05:51:04 Z	vjudge1	Duathlon (APIO18_duathlon)	C++17	31 / 100	83 ms	16240 KB

count_triplets

/*
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) / 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	Correct	4 ms	7380 KB	Output is correct
2	Correct	4 ms	7252 KB	Output is correct
3	Correct	4 ms	7252 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Incorrect	4 ms	7380 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	15284 KB	Output is correct
2	Correct	51 ms	15316 KB	Output is correct
3	Correct	58 ms	14588 KB	Output is correct
4	Correct	52 ms	16240 KB	Output is correct
5	Correct	50 ms	14804 KB	Output is correct
6	Correct	58 ms	15276 KB	Output is correct
7	Correct	56 ms	14136 KB	Output is correct
8	Correct	52 ms	14368 KB	Output is correct
9	Correct	62 ms	13504 KB	Output is correct
10	Correct	72 ms	13880 KB	Output is correct
11	Correct	41 ms	12432 KB	Output is correct
12	Correct	43 ms	12384 KB	Output is correct
13	Correct	37 ms	12260 KB	Output is correct
14	Correct	38 ms	12156 KB	Output is correct
15	Correct	32 ms	11592 KB	Output is correct
16	Correct	25 ms	11476 KB	Output is correct
17	Correct	6 ms	8276 KB	Output is correct
18	Correct	6 ms	8276 KB	Output is correct
19	Correct	6 ms	8276 KB	Output is correct
20	Correct	6 ms	8276 KB	Output is correct
21	Correct	6 ms	8276 KB	Output is correct
22	Correct	6 ms	8268 KB	Output is correct

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	4 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	5 ms	7412 KB	Output is correct
9	Correct	5 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	6 ms	7400 KB	Output is correct
13	Correct	4 ms	7380 KB	Output is correct
14	Correct	4 ms	7380 KB	Output is correct
15	Correct	4 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	5 ms	7380 KB	Output is correct
19	Correct	4 ms	7380 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	57 ms	12088 KB	Output is correct
2	Correct	48 ms	11992 KB	Output is correct
3	Correct	47 ms	12076 KB	Output is correct
4	Correct	52 ms	12072 KB	Output is correct
5	Correct	47 ms	11980 KB	Output is correct
6	Correct	83 ms	15728 KB	Output is correct
7	Correct	72 ms	14796 KB	Output is correct
8	Correct	69 ms	14020 KB	Output is correct
9	Correct	63 ms	13488 KB	Output is correct
10	Correct	50 ms	11992 KB	Output is correct
11	Correct	53 ms	12092 KB	Output is correct
12	Correct	52 ms	12048 KB	Output is correct
13	Correct	53 ms	11984 KB	Output is correct
14	Correct	40 ms	11848 KB	Output is correct
15	Correct	38 ms	11548 KB	Output is correct
16	Correct	26 ms	10708 KB	Output is correct
17	Correct	29 ms	12276 KB	Output is correct
18	Correct	34 ms	12244 KB	Output is correct
19	Correct	37 ms	12172 KB	Output is correct
20	Correct	33 ms	12172 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	4 ms	7380 KB	Output is correct
3	Incorrect	4 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	61 ms	12056 KB	Output is correct
2	Correct	57 ms	11964 KB	Output is correct
3	Incorrect	52 ms	11568 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #710225

Compilation message