oj.uz

Submission #393331

# Submission time Handle Problem Language Result Execution time Memory
393331 2021-04-23T08:02:21 Z parsabahrami Duathlon (APIO18_duathlon) C++17
23 / 100
 127 ms 20164 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 &= SZ(adj[v]) > 1;
    for (int u : adj[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 += c * (c - 1) * (c - 2) / 3;
            else ret += 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:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d%d", &fr[i], &to[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 20164 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 5 ms 6608 KB Output is correct
4 Correct 5 ms 6604 KB Output is correct
5 Correct 5 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 6668 KB Output is correct
9 Correct 5 ms 6604 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct
12 Correct 6 ms 6604 KB Output is correct
13 Correct 5 ms 6604 KB Output is correct
14 Correct 4 ms 6560 KB Output is correct
15 Correct 4 ms 6604 KB Output is correct
16 Correct 4 ms 6564 KB Output is correct
17 Correct 5 ms 6604 KB Output is correct
18 Correct 4 ms 6604 KB Output is correct
19 Correct 6 ms 6604 KB Output is correct
20 Correct 4 ms 6596 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 11752 KB Output is correct
2 Correct 103 ms 11756 KB Output is correct
3 Correct 99 ms 11688 KB Output is correct
4 Correct 101 ms 11752 KB Output is correct
5 Correct 105 ms 11684 KB Output is correct
6 Correct 118 ms 16764 KB Output is correct
7 Correct 127 ms 14960 KB Output is correct
8 Correct 120 ms 14204 KB Output is correct
9 Correct 101 ms 13252 KB Output is correct
10 Correct 94 ms 11716 KB Output is correct
11 Correct 84 ms 12096 KB Output is correct
12 Correct 82 ms 12072 KB Output is correct
13 Correct 95 ms 12120 KB Output is correct
14 Correct 82 ms 11864 KB Output is correct
15 Correct 65 ms 11660 KB Output is correct
16 Correct 47 ms 10692 KB Output is correct
17 Correct 61 ms 12448 KB Output is correct
18 Correct 68 ms 12432 KB Output is correct
19 Correct 59 ms 12392 KB Output is correct
20 Correct 56 ms 12356 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6608 KB Output is correct
2 Correct 5 ms 6648 KB Output is correct
3 Incorrect 5 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 105 ms 11716 KB Output is correct
2 Correct 103 ms 11708 KB Output is correct
3 Incorrect 94 ms 13236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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