oj.uz

Submission #393337

# Submission time Handle Problem Language Result Execution time Memory
393337 2021-04-23T08:09:36 Z parsabahrami Duathlon (APIO18_duathlon) C++17
31 / 100
 126 ms 20216 KB 
/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10;
int n, m, c, B[N], sub[N], M[N], fr[N], H[N], low[N], to[N], S[N], rt[N]; 
vector<int> adj[N]; ll ret = 0; int f = 1;

ll C2(ll x) {
    x = max(0ll, x);
    return x * (x - 1) >> 1;
}

void preDFS(int v, int p = 0) {
    H[v] = H[p] + 1, low[v] = H[v];
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v;
        if (!H[u]) {
            preDFS(u, v);
            low[v] = min(low[u], low[v]);
            if (low[u] > H[v]) B[id] = 1;
        } else if (u != p) 
            low[v] = min(low[v], H[u]);
    }
}

int Find(int v) {
    return !rt[v] ? v : rt[v] = Find(rt[v]);
}

void Union(int u, int v) {
    u = Find(u), v = Find(v);
    if (u == v) return;
    S[v] += S[u];
    rt[u] = v;
}

void DFS(int v, int p = -1) {
    H[v] = 1, ret += S[v] * (S[v] - 1) * (S[v] - 2);
    c += S[v]; sub[v] = S[v];
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v;
        if (u != p) 
            DFS(u, v), sub[v] += sub[u];
    }
}

void SFD(int v, int p = -1) {
    ll tot = 0;
    tot += C2(c - S[v]);
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v;
        if (u != p) 
           tot -= C2(sub[u]);
    }
    tot -= C2(c - sub[v]);
    ret += tot * 2;
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v; 
        if (u != p) SFD(u, v);
    }
    ret += 2ll * (c - S[v]) * 1ll * ((S[v] - 1) * 1ll * (S[v] - 2) + (S[v] - 1));
}

void shitDFS(int v) {
    M[v] = 1, c++; f &= bool(SZ(adj[v]) > 1);
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v;
        if (!M[u]) shitDFS(u);
    }
}

void sub3() {
    for (int i = 1; i <= n; i++) 
        if (!M[i]) {
            c = 0, f = 1;
            shitDFS(i);
            if (!f) ret += 1ll * c * (c - 1) * (c - 2) / 3;
            else ret += 1ll * c * (c - 1) * (c - 2);
        }
    printf("%lld\n", ret);
    exit(0);
}

int main() {
    fill(S, S + N, 1);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &fr[i], &to[i]);
        adj[fr[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) 
        if (!H[i]) preDFS(i);
    for (int i = 1; i <= m; i++) {
        if (!B[i]) 
            sub3(), Union(fr[i], to[i]);
    }
    for (int i = 1; i <= n; i++) 
        adj[i] = {};
    for (int i = 1; i <= m; i++) 
        if (B[i]) {
            adj[fr[i] = Find(fr[i])].push_back(i);
            adj[to[i] = Find(to[i])].push_back(i);
        }
    memset(H, 0, sizeof H);
    for (int i = 1; i <= n; i++) 
        if (!rt[i] && !H[i]) {
            c = 0;
            DFS(i);
            SFD(i);
        }
    printf("%lld\n", ret);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         scanf("%d%d", &fr[i], &to[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Incorrect 3 ms 5708 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 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Incorrect 3 ms 5708 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 88 ms 20216 KB Output is correct
2 Correct 126 ms 20196 KB Output is correct
3 Correct 110 ms 15896 KB Output is correct
4 Correct 86 ms 18220 KB Output is correct
5 Correct 85 ms 14408 KB Output is correct
6 Correct 91 ms 14344 KB Output is correct
7 Correct 117 ms 13068 KB Output is correct
8 Correct 79 ms 13892 KB Output is correct
9 Correct 75 ms 12192 KB Output is correct
10 Correct 74 ms 13008 KB Output is correct
11 Correct 69 ms 11136 KB Output is correct
12 Correct 70 ms 10936 KB Output is correct
13 Correct 82 ms 10836 KB Output is correct
14 Correct 65 ms 10852 KB Output is correct
15 Correct 39 ms 10152 KB Output is correct
16 Correct 40 ms 10032 KB Output is correct
17 Correct 7 ms 7396 KB Output is correct
18 Correct 7 ms 7372 KB Output is correct
19 Correct 7 ms 7372 KB Output is correct
20 Correct 7 ms 7312 KB Output is correct
21 Correct 7 ms 7280 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 11700 KB Output is correct
2 Correct 88 ms 11668 KB Output is correct
3 Correct 88 ms 11708 KB Output is correct
4 Correct 101 ms 11672 KB Output is correct
5 Correct 119 ms 11716 KB Output is correct
6 Correct 108 ms 16756 KB Output is correct
7 Correct 116 ms 15044 KB Output is correct
8 Correct 105 ms 14164 KB Output is correct
9 Correct 115 ms 13308 KB Output is correct
10 Correct 95 ms 11716 KB Output is correct
11 Correct 102 ms 11972 KB Output is correct
12 Correct 88 ms 11956 KB Output is correct
13 Correct 90 ms 11972 KB Output is correct
14 Correct 77 ms 11716 KB Output is correct
15 Correct 75 ms 11520 KB Output is correct
16 Correct 54 ms 10412 KB Output is correct
17 Correct 53 ms 12188 KB Output is correct
18 Correct 52 ms 12220 KB Output is correct
19 Correct 58 ms 12184 KB Output is correct
20 Correct 77 ms 12244 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 11760 KB Output is correct
2 Correct 113 ms 11708 KB Output is correct
3 Incorrect 90 ms 11444 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 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Incorrect 3 ms 5708 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 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Incorrect 3 ms 5708 KB Output isn't correct
8 Halted 0 ms 0 KB -