제출 #1331070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1331070		i_am_blindfold	Duathlon (APIO18_duathlon)	C++20	0 / 100	38 ms	18212 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

vector<pair<int, int>> adj[N];
vector<int> vis(N, 0), siz(N, 1), tin(N), low(N);
long long ans = 0;

void dfs(int u, int ip, int& t, int n) {
    low[u] = tin[u] = t++, vis[u] = 1;
    int sz = n - 1;
    for (auto &[v, i]: adj[u]) {
        if (i == ip) continue;
        if (!vis[v]) {
            dfs(v, i, t, n);
            siz[u] += siz[v];
            low[u] = min(low[u], low[v]);
            if (low[v] >= tin[u]) {
                sz -= siz[v];
                ans += 2LL * (sz * siz[v] + n * (t - tin[u] - 1) * (t - tin[u] - 2)) - (t - tin[u]) * (t - tin[u] - 1) * (t - tin[u] - 2);
                t = tin[u] + 1;
            } 
        } else {
            low[u] = min(low[u], tin[v]); 
        }
    }
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    int timer = 0;
    dfs(1, - 1, timer, n);

    cout << ans << '\n';
    
    return 0;
}

• 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