Submission #159449

#	Time	Username	Problem	Language	Result	Execution time	Memory
159449		Minnakhmetov	Duathlon (APIO18_duathlon)	C++14	31 / 100	146 ms	21140 KiB

count_triplets

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;
 
struct E {
    int to, i;
};
 
const int N = 1e5 + 5;
vector<E> g[N];
vector<int> g2[N], t[N];
int tin[N], mt[N], col[N], sz[N], sum[N];
int timer = 0, n, m;
bool used[N];
 
void dfs(int node, int anc) {
    used[node] = 1;
    tin[node] = ++timer;
    mt[node] = tin[node];
    for (E e : g[node]) {
        if (e.i != anc) {
 
            if (!used[e.to]) {
                dfs(e.to, e.i);
            }
 
            mt[node] = min(mt[node], mt[e.to]);
 
            if (mt[e.to] <= tin[node]) {
                g2[node].push_back(e.to);
                g2[e.to].push_back(node);
            }
        }
    }
}
 
void deep(int node, int c) {
    col[node] = c;
    used[node] = 1;
 
    sz[col[node]]++;
 
    for (int to : g2[node]) {
        if (!used[to]) {
            deep(to, c);
        }
    }
 
    for (E e : g[node]) {
        if (used[e.to] && col[e.to] != col[node]) {
            t[col[node]].push_back(col[e.to]);
            t[col[e.to]].push_back(col[node]);
        }
    }
}
 
ll ans = 0;
 
int walk(int node, int anc) {
    int s = sz[node];
    for (int to : t[node]) {
        if (to != anc) {
            s += walk(to, node);
        }
    }
    return s;
}
 
void dive(int node, int anc, int whole) {
    ans += sz[node] * (ll)(sz[node] - 1) * (sz[node] - 2);
 
    sum[node] = sz[node];
 
    used[node] = 1;
 
    for (int to : t[node]) {
        if (to != anc) {
            dive(to, node, whole);
            sum[node] += sum[to];
        }
    }
 
    for (int to : t[node]) {
        int s = 0;
        if (to == anc)
            s = whole - sum[node];
        else
            s = sum[to];
 
        ans += sz[node] * (ll)s * (whole - s - sz[node]);
 
        ans += (sz[node] * (ll)(sz[node] - 1) - sz[node] + 1) * s * 2;
    }
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }
 
    int cc = 0;
 
    fill(used, used + n, 0);
 
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            deep(i, cc++);
        }
    }
 
    fill(used, used + cc, 0);
 
    for (int i = 0; i < cc; i++) {
        if (!used[i]) {
            dive(i, -1, walk(i, -1));
        }
    }
 
    cout << ans;
 
 
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10