oj.uz

Submission #393268

# Submission time Handle Problem Language Result Execution time Memory
393268 2021-04-23T05:46:22 Z parsabahrami Duathlon (APIO18_duathlon) C++17
23 / 100
 132 ms 17412 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 = 1e5 + 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 2 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Incorrect 2 ms 3404 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 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Incorrect 2 ms 3404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 17412 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 3 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3532 KB Output is correct
5 Correct 3 ms 3536 KB Output is correct
6 Correct 3 ms 3532 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 3 ms 3532 KB Output is correct
9 Correct 4 ms 3532 KB Output is correct
10 Correct 3 ms 3404 KB Output is correct
11 Correct 3 ms 3404 KB Output is correct
12 Correct 3 ms 3468 KB Output is correct
13 Correct 3 ms 3448 KB Output is correct
14 Correct 3 ms 3444 KB Output is correct
15 Correct 3 ms 3404 KB Output is correct
16 Correct 3 ms 3404 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 3 ms 3404 KB Output is correct
19 Correct 3 ms 3500 KB Output is correct
20 Correct 3 ms 3532 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8604 KB Output is correct
2 Correct 110 ms 8536 KB Output is correct
3 Correct 90 ms 8600 KB Output is correct
4 Correct 90 ms 8568 KB Output is correct
5 Correct 119 ms 8588 KB Output is correct
6 Correct 124 ms 13508 KB Output is correct
7 Correct 110 ms 11880 KB Output is correct
8 Correct 118 ms 10936 KB Output is correct
9 Correct 107 ms 10204 KB Output is correct
10 Correct 132 ms 8600 KB Output is correct
11 Correct 93 ms 9796 KB Output is correct
12 Correct 91 ms 9808 KB Output is correct
13 Correct 92 ms 9824 KB Output is correct
14 Correct 75 ms 9544 KB Output is correct
15 Correct 69 ms 9112 KB Output is correct
16 Correct 49 ms 7672 KB Output is correct
17 Correct 73 ms 10172 KB Output is correct
18 Correct 49 ms 10068 KB Output is correct
19 Correct 56 ms 10152 KB Output is correct
20 Correct 55 ms 10088 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 8612 KB Output is correct
2 Correct 119 ms 8556 KB Output is correct
3 Runtime error 60 ms 14896 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 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Incorrect 2 ms 3404 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 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Incorrect 2 ms 3404 KB Output isn't correct
8 Halted 0 ms 0 KB -