Submission #217599

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217599	2020-03-30T10:32:13 Z	VEGAnn	Duathlon (APIO18_duathlon)	C++14	31 / 100	125 ms	19772 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]) - 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	9 ms	5168 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	9 ms	5168 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	90 ms	18424 KB	Output is correct
2	Correct	85 ms	19772 KB	Output is correct
3	Correct	114 ms	17832 KB	Output is correct
4	Correct	96 ms	19064 KB	Output is correct
5	Correct	90 ms	15992 KB	Output is correct
6	Correct	96 ms	16760 KB	Output is correct
7	Correct	101 ms	15864 KB	Output is correct
8	Correct	97 ms	16504 KB	Output is correct
9	Correct	100 ms	15096 KB	Output is correct
10	Correct	106 ms	15480 KB	Output is correct
11	Correct	74 ms	13688 KB	Output is correct
12	Correct	84 ms	13564 KB	Output is correct
13	Correct	65 ms	13500 KB	Output is correct
14	Correct	66 ms	13264 KB	Output is correct
15	Correct	70 ms	12792 KB	Output is correct
16	Correct	53 ms	12536 KB	Output is correct
17	Correct	9 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	11 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	5248 KB	Output is correct
2	Correct	8 ms	5120 KB	Output is correct
3	Correct	8 ms	5120 KB	Output is correct
4	Correct	8 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	8 ms	5248 KB	Output is correct
8	Correct	10 ms	5248 KB	Output is correct
9	Correct	7 ms	5248 KB	Output is correct
10	Correct	7 ms	5120 KB	Output is correct
11	Correct	8 ms	5120 KB	Output is correct
12	Correct	7 ms	5248 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	8 ms	5120 KB	Output is correct
18	Correct	7 ms	5120 KB	Output is correct
19	Correct	7 ms	5120 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	14456 KB	Output is correct
2	Correct	95 ms	14456 KB	Output is correct
3	Correct	96 ms	14456 KB	Output is correct
4	Correct	118 ms	14584 KB	Output is correct
5	Correct	99 ms	14456 KB	Output is correct
6	Correct	125 ms	18552 KB	Output is correct
7	Correct	115 ms	17144 KB	Output is correct
8	Correct	113 ms	16376 KB	Output is correct
9	Correct	108 ms	15736 KB	Output is correct
10	Correct	105 ms	14584 KB	Output is correct
11	Correct	93 ms	14456 KB	Output is correct
12	Correct	98 ms	14456 KB	Output is correct
13	Correct	94 ms	14456 KB	Output is correct
14	Correct	81 ms	14200 KB	Output is correct
15	Correct	88 ms	13816 KB	Output is correct
16	Correct	51 ms	12280 KB	Output is correct
17	Correct	62 ms	15088 KB	Output is correct
18	Correct	60 ms	15096 KB	Output is correct
19	Correct	62 ms	15340 KB	Output is correct
20	Correct	61 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	7 ms	5248 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	96 ms	14456 KB	Output is correct
2	Correct	101 ms	14456 KB	Output is correct
3	Incorrect	97 ms	13508 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	9 ms	5168 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	9 ms	5168 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 #217599

Compilation message