Submission #217644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217644	2020-03-30T11:34:17 Z	VEGAnn	Duathlon (APIO18_duathlon)	C++14	31 / 100	1000 ms	20576 KB

count_triplets

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
const int oo = 2e9;
vector<int> g[N];
vector<pii> 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 (pii u : gr[v]){
        if (u.sd == p) continue;

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

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 it = 0; it < sz(gr[v]); ){

        int j = it;
        ll sim = 0;

        while (j < sz(g[v]) && gr[v][it].ft == gr[v][j].ft){
            int u = gr[v][j].sd;
            if (u != p) {
                dfs2(u, v);
                ans += sim * ll(nw_siz[u]);
                sim += ll(nw_siz[u]);
            } else {
                ans += sim * (SZ - ll(nw_siz[v]));
                sim += (SZ - ll(nw_siz[v]));
            }
            j++;
        }

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

        sum += sim;

        it = j;
    }
}

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(MP(U[i], y));
            gr[y].PB(MP(V[i], x));
        }

    fill(mrk, mrk + n, 0);
    for (int i = 0; i < n; i++)
        if (sz(g[i])){
            sort(all(gr[i]));
        }

    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	8 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	10 ms	5120 KB	Output is correct
5	Correct	10 ms	5120 KB	Output is correct
6	Correct	7 ms	5120 KB	Output is correct
7	Execution timed out	1085 ms	5120 KB	Time limit exceeded
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	8 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	10 ms	5120 KB	Output is correct
5	Correct	10 ms	5120 KB	Output is correct
6	Correct	7 ms	5120 KB	Output is correct
7	Execution timed out	1085 ms	5120 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	19732 KB	Output is correct
2	Correct	112 ms	19704 KB	Output is correct
3	Correct	159 ms	17912 KB	Output is correct
4	Correct	147 ms	19064 KB	Output is correct
5	Correct	191 ms	16012 KB	Output is correct
6	Correct	189 ms	17272 KB	Output is correct
7	Correct	178 ms	16096 KB	Output is correct
8	Correct	178 ms	16568 KB	Output is correct
9	Correct	163 ms	15232 KB	Output is correct
10	Correct	160 ms	15456 KB	Output is correct
11	Correct	123 ms	13772 KB	Output is correct
12	Correct	114 ms	13536 KB	Output is correct
13	Correct	107 ms	13560 KB	Output is correct
14	Correct	117 ms	13244 KB	Output is correct
15	Correct	83 ms	12792 KB	Output is correct
16	Correct	78 ms	12536 KB	Output is correct
17	Correct	11 ms	7168 KB	Output is correct
18	Correct	11 ms	7168 KB	Output is correct
19	Correct	11 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	11 ms	7168 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	5248 KB	Output is correct
2	Correct	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 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	5220 KB	Output is correct
7	Correct	8 ms	5248 KB	Output is correct
8	Correct	9 ms	5248 KB	Output is correct
9	Correct	9 ms	5296 KB	Output is correct
10	Correct	9 ms	5248 KB	Output is correct
11	Correct	8 ms	5248 KB	Output is correct
12	Correct	9 ms	5248 KB	Output is correct
13	Correct	8 ms	5248 KB	Output is correct
14	Correct	10 ms	5168 KB	Output is correct
15	Correct	8 ms	5120 KB	Output is correct
16	Correct	8 ms	5248 KB	Output is correct
17	Correct	9 ms	5248 KB	Output is correct
18	Correct	10 ms	5248 KB	Output is correct
19	Correct	8 ms	5248 KB	Output is correct
20	Correct	8 ms	5248 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	16276 KB	Output is correct
2	Correct	186 ms	16248 KB	Output is correct
3	Correct	156 ms	16248 KB	Output is correct
4	Correct	196 ms	16352 KB	Output is correct
5	Correct	152 ms	16248 KB	Output is correct
6	Correct	210 ms	20576 KB	Output is correct
7	Correct	198 ms	19520 KB	Output is correct
8	Correct	190 ms	18552 KB	Output is correct
9	Correct	272 ms	17656 KB	Output is correct
10	Correct	163 ms	16376 KB	Output is correct
11	Correct	159 ms	16248 KB	Output is correct
12	Correct	154 ms	16248 KB	Output is correct
13	Correct	181 ms	16248 KB	Output is correct
14	Correct	126 ms	15736 KB	Output is correct
15	Correct	118 ms	15100 KB	Output is correct
16	Correct	74 ms	12920 KB	Output is correct
17	Correct	96 ms	16748 KB	Output is correct
18	Correct	93 ms	16756 KB	Output is correct
19	Correct	87 ms	16604 KB	Output is correct
20	Correct	95 ms	16744 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	Execution timed out	1089 ms	5120 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	16248 KB	Output is correct
2	Correct	163 ms	16104 KB	Output is correct
3	Execution timed out	1090 ms	15224 KB	Time limit exceeded
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	8 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	10 ms	5120 KB	Output is correct
5	Correct	10 ms	5120 KB	Output is correct
6	Correct	7 ms	5120 KB	Output is correct
7	Execution timed out	1085 ms	5120 KB	Time limit exceeded
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	8 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	10 ms	5120 KB	Output is correct
5	Correct	10 ms	5120 KB	Output is correct
6	Correct	7 ms	5120 KB	Output is correct
7	Execution timed out	1085 ms	5120 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Submission #217644

Compilation message