oj.uz

Submission #1116935

# Submission time Handle Problem Language Result Execution time Memory
1116935 2024-11-22T15:41:00 Z adaawf Duathlon (APIO18_duathlon) C++17
31 / 100
 77 ms 31776 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<pair<int, int>, int> mm;
vector<int> g[100005], gg[200005], v;
int tin[100005], low[100005], dd[100005], da[100005], z = 0, db[100005], hh;
long long int s[200005], f[200005], kk = 0, n, res = 0;
void dfs(int x, int p) {
    tin[x] = low[x] = ++z;
    v.push_back(x);
    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]) {
                hh++;
                while (v.back() != x) {
                    gg[v.back()].push_back(hh);
                    gg[hh].push_back(v.back());
                    v.pop_back();
                }
                gg[hh].push_back(x);
                gg[x].push_back(hh);
            }
            c++;
        }
        else low[x] = min(low[x], tin[w]);
    }
    if (p == -1 && c >= 2) {

    }
}
void dfs3(int x, int p) {
    db[x] = 1;
    if (x <= n) kk++;
    for (int w : gg[x]) {
        if (w == p) continue;
        dfs3(w, x);
    }
}
void dfs4(int x, int p) {
    s[x] = (x <= n);
    for (int w : gg[x]) {
        if (w == p) continue;
        dfs4(w, x);
        s[x] += s[w];
    }
    for (int w : gg[x]) {
        long long int k;
        if (w == p) k = kk - s[x];
        else k = s[w];
        if (x > n) res -= k * (k - 1) * (gg[x].size() - 1);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int 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);
    }
    hh = n;
    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0) {
            dfs(i, -1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (db[i] == 0) {
            kk = 0;
            dfs3(i, -1);
            res += kk * (kk - 1) * (kk - 2);
            dfs4(i, -1);
        }
    }
    cout << res;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:12:9: warning: unused variable 'fl' [-Wunused-variable]
   12 |     int fl = 0, c = 0;
      |         ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12220 KB Output is correct
3 Correct 3 ms 12368 KB Output is correct
4 Correct 4 ms 12368 KB Output is correct
5 Correct 3 ms 12220 KB Output is correct
6 Correct 4 ms 12368 KB Output is correct
7 Incorrect 4 ms 12536 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 51 ms 27072 KB Output is correct
2 Correct 58 ms 27072 KB Output is correct
3 Correct 72 ms 27332 KB Output is correct
4 Correct 60 ms 27040 KB Output is correct
5 Correct 77 ms 25328 KB Output is correct
6 Correct 72 ms 27076 KB Output is correct
7 Correct 56 ms 24904 KB Output is correct
8 Correct 50 ms 25416 KB Output is correct
9 Correct 51 ms 23564 KB Output is correct
10 Correct 50 ms 23880 KB Output is correct
11 Correct 48 ms 21136 KB Output is correct
12 Correct 49 ms 20960 KB Output is correct
13 Correct 43 ms 20936 KB Output is correct
14 Correct 56 ms 20568 KB Output is correct
15 Correct 30 ms 19660 KB Output is correct
16 Correct 36 ms 19452 KB Output is correct
17 Correct 5 ms 12760 KB Output is correct
18 Correct 5 ms 12760 KB Output is correct
19 Correct 6 ms 12760 KB Output is correct
20 Correct 5 ms 12804 KB Output is correct
21 Correct 5 ms 12752 KB Output is correct
22 Correct 5 ms 12752 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 21840 KB Output is correct
2 Correct 70 ms 22728 KB Output is correct
3 Correct 62 ms 22936 KB Output is correct
4 Correct 74 ms 23100 KB Output is correct
5 Correct 69 ms 22952 KB Output is correct
6 Correct 67 ms 31776 KB Output is correct
7 Correct 75 ms 28632 KB Output is correct
8 Correct 75 ms 27208 KB Output is correct
9 Correct 69 ms 25672 KB Output is correct
10 Correct 66 ms 22856 KB Output is correct
11 Correct 74 ms 23128 KB Output is correct
12 Correct 71 ms 23216 KB Output is correct
13 Correct 69 ms 23112 KB Output is correct
14 Correct 68 ms 22600 KB Output is correct
15 Correct 50 ms 21968 KB Output is correct
16 Correct 38 ms 19272 KB Output is correct
17 Correct 44 ms 23752 KB Output is correct
18 Correct 47 ms 23620 KB Output is correct
19 Correct 46 ms 23996 KB Output is correct
20 Correct 39 ms 23632 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 21860 KB Output is correct
2 Correct 62 ms 21688 KB Output is correct
3 Incorrect 54 ms 21576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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