oj.uz

Submission #1113437

# Submission time Handle Problem Language Result Execution time Memory
1113437 2024-11-16T14:57:09 Z adaawf Duathlon (APIO18_duathlon) C++17
31 / 100
 84 ms 28144 KB 
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> e[200005];
vector<pair<int, int>> g[100005];
long long int dd[100005], a[100005], b[100005], tin[100005], f[100005], s[100005], z = 0;
vector<int> gg[100005], v;
void dfs(int x, int p) {
    tin[x] = f[x] = ++z;
    for (auto w : g[x]) {
        if (w.first == p) continue;
        if (tin[w.first]) {
            f[x] = min(f[x], tin[w.first]);
        }
        else {
            dfs(w.first, x);
            f[x] = min(f[x], f[w.first]);
            if (tin[x] < f[w.first]) {
                dd[w.second] = 1;
            }
        }
    }
}
void dfs2(int x, int h) {
    b[x] = h;
    a[h]++;
    for (auto w : g[x]) {
        if (b[w.first] || dd[w.second]) continue;
        dfs2(w.first, h);
    }
}
long long int res = 0, d = 0;
void dfs3(int x, int p) {
    v.push_back(x);
    s[x] = a[x];
    d += a[x];
    tin[x] = 1;
    long long int h = 0;
    for (int w : gg[x]) {
        if (w == p) continue;
        dfs3(w, x);
        s[x] += s[w];
    }
}
void dfs4(int x, int p) {
    long long int h = 0;
    for (int w : gg[x]) {
        long long int k;
        if (w == p) {
            k = d - s[x];
        }
        else {
            dfs4(w, x);
            k = s[w];
        }
        res += h * k;
        h += k;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0) {
            dfs(i, -1);
        }
    }
    z = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {
            z++;
            dfs2(i, z);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (dd[i] == 1) {
            gg[b[e[i].first]].push_back(b[e[i].second]);
            gg[b[e[i].second]].push_back(b[e[i].first]);
        }
    }
    for (int i = 1; i <= z; i++) tin[i] = 0;
    for (int i = 1; i <= z; i++) {
        if (tin[i] == 0) {
            v.clear();
            d = 0;
            dfs3(i, -1);
            dfs4(i, -1);
            for (int w : v) {
                //cout << w << " " << a[w] << " " << s[w] << '\n';
                res += (a[w] - 1) * a[w] * a[w] / 2;
                res += d - a[w];
                res += (a[w] - 1) * a[w] * (d - a[w]);
            }
            res -= d * (d - 1);
        }
    }
    cout << res * 2;
}

Compilation message

count_triplets.cpp: In function 'void dfs3(int, int)':
count_triplets.cpp:38:19: warning: unused variable 'h' [-Wunused-variable]
   38 |     long long int h = 0;
      |                   ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8832 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 11000 KB Output is correct
7 Incorrect 2 ms 10900 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 40 ms 20816 KB Output is correct
2 Correct 46 ms 22104 KB Output is correct
3 Correct 50 ms 20696 KB Output is correct
4 Correct 43 ms 21396 KB Output is correct
5 Correct 42 ms 18764 KB Output is correct
6 Correct 48 ms 19544 KB Output is correct
7 Correct 51 ms 18392 KB Output is correct
8 Correct 69 ms 19416 KB Output is correct
9 Correct 63 ms 17736 KB Output is correct
10 Correct 60 ms 17348 KB Output is correct
11 Correct 47 ms 15456 KB Output is correct
12 Correct 55 ms 15432 KB Output is correct
13 Correct 41 ms 15432 KB Output is correct
14 Correct 41 ms 15092 KB Output is correct
15 Correct 38 ms 14928 KB Output is correct
16 Correct 34 ms 14428 KB Output is correct
17 Correct 8 ms 9040 KB Output is correct
18 Correct 8 ms 9040 KB Output is correct
19 Correct 12 ms 9040 KB Output is correct
20 Correct 8 ms 9040 KB Output is correct
21 Correct 5 ms 10832 KB Output is correct
22 Correct 5 ms 10832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11008 KB Output is correct
2 Correct 3 ms 11000 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 4 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct
8 Correct 4 ms 5200 KB Output is correct
9 Correct 5 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct
11 Correct 2 ms 10832 KB Output is correct
12 Correct 5 ms 5200 KB Output is correct
13 Correct 5 ms 5200 KB Output is correct
14 Correct 5 ms 5304 KB Output is correct
15 Correct 3 ms 10832 KB Output is correct
16 Correct 3 ms 10832 KB Output is correct
17 Correct 4 ms 11000 KB Output is correct
18 Correct 3 ms 10832 KB Output is correct
19 Correct 4 ms 10832 KB Output is correct
20 Correct 3 ms 10836 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18296 KB Output is correct
2 Correct 57 ms 19684 KB Output is correct
3 Correct 60 ms 19664 KB Output is correct
4 Correct 74 ms 19660 KB Output is correct
5 Correct 57 ms 19728 KB Output is correct
6 Correct 66 ms 23248 KB Output is correct
7 Correct 84 ms 22192 KB Output is correct
8 Correct 66 ms 21356 KB Output is correct
9 Correct 70 ms 20680 KB Output is correct
10 Correct 70 ms 19496 KB Output is correct
11 Correct 64 ms 19368 KB Output is correct
12 Correct 56 ms 19128 KB Output is correct
13 Correct 65 ms 19348 KB Output is correct
14 Correct 51 ms 18504 KB Output is correct
15 Correct 60 ms 17992 KB Output is correct
16 Correct 38 ms 16160 KB Output is correct
17 Correct 61 ms 20392 KB Output is correct
18 Correct 52 ms 20280 KB Output is correct
19 Correct 57 ms 20400 KB Output is correct
20 Correct 56 ms 20280 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10928 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Incorrect 3 ms 10832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 18332 KB Output is correct
2 Correct 68 ms 19396 KB Output is correct
3 Runtime error 54 ms 28144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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