제출 #1283198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283198		abc123	철인 이종 경기 (APIO18_duathlon)	C++20	0 / 100	1096 ms	8436 KiB

count_triplets

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

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

    vector<vector<int>> adj(n + 1);
    vector<vector<int>> radj(n + 1);  // reverse graph for counting backward paths

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

    // Function to count number of nodes reachable from start
    auto bfs_count = [&](int start) {
        vector<bool> visited(n + 1, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;
        int count = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            count++;
            for (int neigh : adj[node]) {
                if (!visited[neigh]) {
                    visited[neigh] = true;
                    q.push(neigh);
                }
            }
        }
        return count;
    };

    long long result = 0;

    // For each node c, calculate the number of ways to pick s and f
    // such that the simple path s -> c -> f exists.
    // Since the graph is undirected and simple, a double counting using BFS counts suffices
    for (int c = 1; c <= n; c++) {
        // Count of nodes reachable from c (including c)
        long long reachable_count = bfs_count(c);
        // subtract 1 for c itself to count s and f distinct from c
        if(reachable_count > 1)
            result += (reachable_count - 1) * (reachable_count - 2); 
        // The formula counts combinations for s and f around c along paths.
    }

    cout << result << "\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