Submission #217604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217604	2020-03-30T10:41:57 Z	VEGAnn	Duathlon (APIO18_duathlon)	C++14	31 / 100	129 ms	18552 KB

count_triplets

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
const int oo = 2e9;
vector<int> g[N], gr[N];
int n, m, tin[N], fup[N], tt = 0, U[M], V[M], pr[N], siz[N];
int nw_siz[N];
bool mrk[N], bridge[M];
ll ans = 0, SZ;

void dfs(int v, int p){
    mrk[v] = 1;
    tin[v] = fup[v] = ++tt;

    for (int nm : g[v]){
        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (u == p) continue;

        if (mrk[u])
            fup[v] = min(fup[v], tin[u]);
        else {
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);

            if (fup[u] > tin[v])
                bridge[nm] = 1;
        }
    }
}

int get(int x) { return (x == pr[x] ? x : pr[x] = get(pr[x])); }

void dfs1(int v, int p){
    nw_siz[v] = siz[v];
    mrk[v] = 1;

    for (int u : gr[v]){
        if (u == p) continue;

        dfs1(u, v);
        nw_siz[v] += nw_siz[u];
    }
}

void dfs2(int v, int p){
    ans += ll(siz[v]) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 2ll) / 2ll; // first

    ans += (SZ - ll(siz[v])) * ((ll(siz[v]) - 2ll) * (ll(siz[v]) - 1ll) + (ll(siz[v]) - 1ll));

    ll sum = 0ll;

    for (int u : gr[v]){
        if (u == p) continue;

        dfs2(u, v);

        ans += sum * ll(siz[v]) * ll(nw_siz[u]);

        sum += nw_siz[u];
    }

    ans += sum * ll(siz[v]) * (SZ - ll(nw_siz[v]));
}

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

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;

        g[U[i]].PB(i);
        g[V[i]].PB(i);
    }

    for (int i = 0; i < n; i++) {
        if (!mrk[i])
            dfs(i, -1);

        pr[i] = i;
        siz[i] = 1;
    }


    for (int i = 0; i < m; i++) {
        if (bridge[i]) continue;

        int x = get(U[i]), y = get(V[i]);

        if (x == y) continue;

        pr[x] = y;
        siz[y] += siz[x];
    }

    for (int i = 0; i < m; i++)
        if (bridge[i]){
            int x = get(U[i]), y = get(V[i]);

            gr[x].PB(y);
            gr[y].PB(x);
        }

    fill(mrk, mrk + n, 0);

    for (int i = 0; i < n; i++){
        if (get(i) != i) continue;
        if (mrk[i]) continue;

        dfs1(i, -1);
        SZ = nw_siz[i];
        dfs2(i, -1);
    }

    cout << ans * 2;

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	7 ms	5120 KB	Output is correct
7	Incorrect	7 ms	5120 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	84 ms	18424 KB	Output is correct
2	Correct	87 ms	18424 KB	Output is correct
3	Correct	96 ms	16632 KB	Output is correct
4	Correct	98 ms	17912 KB	Output is correct
5	Correct	95 ms	14712 KB	Output is correct
6	Correct	100 ms	15480 KB	Output is correct
7	Correct	97 ms	14584 KB	Output is correct
8	Correct	95 ms	15224 KB	Output is correct
9	Correct	126 ms	13808 KB	Output is correct
10	Correct	101 ms	14140 KB	Output is correct
11	Correct	70 ms	12652 KB	Output is correct
12	Correct	81 ms	12408 KB	Output is correct
13	Correct	64 ms	12536 KB	Output is correct
14	Correct	86 ms	12408 KB	Output is correct
15	Correct	51 ms	12024 KB	Output is correct
16	Correct	52 ms	11776 KB	Output is correct
17	Correct	10 ms	7168 KB	Output is correct
18	Correct	10 ms	7168 KB	Output is correct
19	Correct	10 ms	7168 KB	Output is correct
20	Correct	10 ms	7168 KB	Output is correct
21	Correct	10 ms	7168 KB	Output is correct
22	Correct	10 ms	7168 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	14468 KB	Output is correct
2	Correct	100 ms	14456 KB	Output is correct
3	Correct	95 ms	14456 KB	Output is correct
4	Correct	96 ms	14456 KB	Output is correct
5	Correct	98 ms	14456 KB	Output is correct
6	Correct	124 ms	18552 KB	Output is correct
7	Correct	117 ms	17144 KB	Output is correct
8	Correct	118 ms	16376 KB	Output is correct
9	Correct	129 ms	15736 KB	Output is correct
10	Correct	92 ms	14456 KB	Output is correct
11	Correct	93 ms	14456 KB	Output is correct
12	Correct	93 ms	14456 KB	Output is correct
13	Correct	96 ms	14456 KB	Output is correct
14	Correct	99 ms	14328 KB	Output is correct
15	Correct	76 ms	13816 KB	Output is correct
16	Correct	51 ms	12280 KB	Output is correct
17	Correct	60 ms	15088 KB	Output is correct
18	Correct	61 ms	15088 KB	Output is correct
19	Correct	81 ms	15468 KB	Output is correct
20	Correct	66 ms	15096 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	5248 KB	Output is correct
2	Correct	8 ms	5120 KB	Output is correct
3	Incorrect	8 ms	5120 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	14456 KB	Output is correct
2	Correct	110 ms	14328 KB	Output is correct
3	Incorrect	100 ms	13432 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #217604

Compilation message