Submission #393332

#	Time	Username	Problem	Language	Result	Execution time	Memory
393332		parsabahrami	Duathlon (APIO18_duathlon)	C++17	0 / 100	65 ms	16328 KiB

count_triplets

/* 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 += 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);
    }
    sub3();
    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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10