Submission #1116905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116905	2024-11-22T14:34:49 Z	adaawf	Duathlon (APIO18_duathlon)	C++17	31 / 100	1000 ms	1048576 KB

count_triplets

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<pair<int, int>, int> mm;
vector<int> g[100005], gg[200005];
int tin[100005], low[100005], dd[100005], da[100005], z = 0, db[100005];
long long int s[200005], f[200005], hh = 0, kk = 0, ha, res = 0;
void dfs(int x, int p) {
    tin[x] = low[x] = ++z;
    int fl = 0, c = 0;
    for (int w : g[x]) {
        if (w == p) continue;
        if (tin[w] == 0) {
            dfs(w, x);
            low[x] = min(low[x], low[w]);
            if (low[w] >= tin[x]) {
                fl = 1;
            }
            c++;
        }
        else low[x] = min(low[x], tin[w]);
    }
    if (p == -1) {
        if (c >= 2) dd[x] = 1;
    }
    else if (fl == 1) dd[x] = 1;
    hh += dd[x];
    kk++;
}
void dfs2(int x, int h) {
    da[x] = h;
    s[h]++;
    for (int w : g[x]) {
        if (da[w] != 0 || dd[w] == 1) continue;
        dfs2(w, h);
    }
}
void dfs3(int x, int p) {
    db[x] = 1;
    f[x] = s[x];
    for (int w : gg[x]) {
        if (w == p) continue;
        dfs3(w, x);
        f[x] += f[w];
    }
}
void dfs4(int x, int p) {
    long long int h = 0;
    for (int w : gg[x]) {
        if (w != p) dfs4(w, x);
        long long int k;
        if (w == p) k = ha - f[x];
        else k = f[w];
        res += s[w] * h * k;
        res += k * (s[w] - 1) * (s[w] - 1);
        res += s[w] * (s[w] - 1) / 2;
        h += k;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0) {
            hh = kk = 0;
            dfs(i, -1);
            if (hh == 0) {
                res += kk * (kk - 1) * (kk - 2) / 2;
            }
        }
    }
    int zz = 0;
    for (int i = 1; i <= n; i++) {
        if (dd[i] == 1) {
            da[i] = ++zz;
            s[zz] = 1;
            for (int w : g[i]) {
                if (da[w] == 0 && dd[w] == 0) {
                    zz++;
                    dfs2(w, zz);
                }
            }
        }
    }
    for (int i = 1; i <= zz; i++) {
        res += s[i] * (s[i] - 1) * (s[i] - 2) / 2;
    }
    for (int i = 1; i <= n; i++) {
        for (int w : g[i]) {
            int h = da[i], k = da[w];
            if (h == k || mm.count({h, k})) continue;
            gg[h].push_back(k);
            mm[{h, k}] = 1;
        }
    }
    for (int i = 1; i <= zz; i++) {
        if (db[i] == 0) {
            dfs3(i, -1);
            ha = f[i];
            dfs4(i, -1);
        }
    }
    cout << res * 2;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8272 KB	Output is correct
2	Correct	3 ms	8272 KB	Output is correct
3	Correct	3 ms	8272 KB	Output is correct
4	Correct	3 ms	8272 KB	Output is correct
5	Correct	3 ms	8448 KB	Output is correct
6	Correct	3 ms	8272 KB	Output is correct
7	Runtime error	987 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8272 KB	Output is correct
2	Correct	3 ms	8272 KB	Output is correct
3	Correct	3 ms	8272 KB	Output is correct
4	Correct	3 ms	8272 KB	Output is correct
5	Correct	3 ms	8448 KB	Output is correct
6	Correct	3 ms	8272 KB	Output is correct
7	Runtime error	987 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	21832 KB	Output is correct
2	Correct	39 ms	21976 KB	Output is correct
3	Correct	75 ms	28280 KB	Output is correct
4	Correct	61 ms	26696 KB	Output is correct
5	Correct	71 ms	24136 KB	Output is correct
6	Correct	80 ms	27464 KB	Output is correct
7	Correct	99 ms	26952 KB	Output is correct
8	Correct	88 ms	27720 KB	Output is correct
9	Correct	73 ms	26184 KB	Output is correct
10	Correct	71 ms	25356 KB	Output is correct
11	Correct	57 ms	21356 KB	Output is correct
12	Correct	67 ms	21168 KB	Output is correct
13	Correct	74 ms	19984 KB	Output is correct
14	Correct	62 ms	20148 KB	Output is correct
15	Correct	36 ms	17232 KB	Output is correct
16	Correct	35 ms	17492 KB	Output is correct
17	Correct	4 ms	8276 KB	Output is correct
18	Correct	4 ms	8272 KB	Output is correct
19	Correct	4 ms	8272 KB	Output is correct
20	Correct	4 ms	8272 KB	Output is correct
21	Correct	4 ms	10320 KB	Output is correct
22	Correct	4 ms	8272 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	10576 KB	Output is correct
2	Correct	5 ms	10404 KB	Output is correct
3	Correct	4 ms	10576 KB	Output is correct
4	Correct	3 ms	10576 KB	Output is correct
5	Correct	4 ms	10576 KB	Output is correct
6	Correct	4 ms	10576 KB	Output is correct
7	Correct	5 ms	10576 KB	Output is correct
8	Correct	4 ms	10624 KB	Output is correct
9	Correct	4 ms	10576 KB	Output is correct
10	Correct	4 ms	10576 KB	Output is correct
11	Correct	4 ms	10384 KB	Output is correct
12	Correct	4 ms	10384 KB	Output is correct
13	Correct	4 ms	10576 KB	Output is correct
14	Correct	4 ms	10576 KB	Output is correct
15	Correct	4 ms	10588 KB	Output is correct
16	Correct	4 ms	10320 KB	Output is correct
17	Correct	4 ms	10576 KB	Output is correct
18	Correct	3 ms	10372 KB	Output is correct
19	Correct	4 ms	10576 KB	Output is correct
20	Correct	4 ms	10556 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	31048 KB	Output is correct
2	Correct	144 ms	31656 KB	Output is correct
3	Correct	134 ms	31816 KB	Output is correct
4	Correct	123 ms	32000 KB	Output is correct
5	Correct	128 ms	31880 KB	Output is correct
6	Correct	112 ms	36940 KB	Output is correct
7	Correct	156 ms	35000 KB	Output is correct
8	Correct	123 ms	34384 KB	Output is correct
9	Correct	131 ms	33352 KB	Output is correct
10	Correct	127 ms	31560 KB	Output is correct
11	Correct	134 ms	31876 KB	Output is correct
12	Correct	125 ms	31816 KB	Output is correct
13	Correct	132 ms	31820 KB	Output is correct
14	Correct	135 ms	30088 KB	Output is correct
15	Correct	103 ms	28108 KB	Output is correct
16	Correct	49 ms	20552 KB	Output is correct
17	Correct	125 ms	32152 KB	Output is correct
18	Correct	116 ms	32072 KB	Output is correct
19	Correct	130 ms	32188 KB	Output is correct
20	Correct	163 ms	32072 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10576 KB	Output is correct
2	Correct	4 ms	10576 KB	Output is correct
3	Runtime error	884 ms	1048576 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	31920 KB	Output is correct
2	Correct	125 ms	31816 KB	Output is correct
3	Execution timed out	1128 ms	1048576 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8272 KB	Output is correct
2	Correct	3 ms	8272 KB	Output is correct
3	Correct	3 ms	8272 KB	Output is correct
4	Correct	3 ms	8272 KB	Output is correct
5	Correct	3 ms	8448 KB	Output is correct
6	Correct	3 ms	8272 KB	Output is correct
7	Runtime error	987 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8272 KB	Output is correct
2	Correct	3 ms	8272 KB	Output is correct
3	Correct	3 ms	8272 KB	Output is correct
4	Correct	3 ms	8272 KB	Output is correct
5	Correct	3 ms	8448 KB	Output is correct
6	Correct	3 ms	8272 KB	Output is correct
7	Runtime error	987 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Submission #1116905

Compilation message