oj.uz

Submission #393270

# Submission time Handle Problem Language Result Execution time Memory
393270 2021-04-23T05:47:16 Z parsabahrami Duathlon (APIO18_duathlon) C++17
23 / 100
 137 ms 20640 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], fr[N], H[N], low[N], to[N], S[N], rt[N]; 
vector<int> adj[N]; ll ret = 0;

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);
}

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]) 
            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:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         scanf("%d%d", &fr[i], &to[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 20640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 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 6 ms 6604 KB Output is correct
6 Correct 5 ms 6604 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 5 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 5 ms 6604 KB Output is correct
12 Correct 4 ms 6604 KB Output is correct
13 Correct 4 ms 6600 KB Output is correct
14 Correct 5 ms 6648 KB Output is correct
15 Correct 5 ms 6604 KB Output is correct
16 Correct 4 ms 6604 KB Output is correct
17 Correct 4 ms 6604 KB Output is correct
18 Correct 4 ms 6656 KB Output is correct
19 Correct 4 ms 6604 KB Output is correct
20 Correct 4 ms 6604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 11748 KB Output is correct
2 Correct 110 ms 11708 KB Output is correct
3 Correct 87 ms 11716 KB Output is correct
4 Correct 116 ms 11768 KB Output is correct
5 Correct 107 ms 11740 KB Output is correct
6 Correct 137 ms 16904 KB Output is correct
7 Correct 118 ms 15192 KB Output is correct
8 Correct 112 ms 14100 KB Output is correct
9 Correct 100 ms 13276 KB Output is correct
10 Correct 91 ms 11672 KB Output is correct
11 Correct 119 ms 11860 KB Output is correct
12 Correct 105 ms 11708 KB Output is correct
13 Correct 95 ms 11812 KB Output is correct
14 Correct 81 ms 11436 KB Output is correct
15 Correct 74 ms 11332 KB Output is correct
16 Correct 44 ms 10280 KB Output is correct
17 Correct 70 ms 12028 KB Output is correct
18 Correct 58 ms 11964 KB Output is correct
19 Correct 62 ms 11964 KB Output is correct
20 Correct 58 ms 12032 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 11716 KB Output is correct
2 Correct 119 ms 11712 KB Output is correct
3 Incorrect 93 ms 12228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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