Submission #1213330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213330		spike1236	Duathlon (APIO18_duathlon)	C++20	0 / 100	110 ms	28436 KiB

count_triplets

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

static const int MOD = 1000000007;
int N, M;

vector<vector<int>> G;

vector<int> disc, low, stk;
vector<bool> inStack;
int timerTarjan;

vector<vector<int>> blocks;

vector<vector<int>> Tadj;

vector<long long> weightT;

vector<long long> subtree_size;
vector<bool> visitedT;
long long totalBad = 0;

void tarjanDFS(int u, int parent) {
    disc[u] = low[u] = ++timerTarjan;
    stk.push_back(u);
    inStack[u] = true;

    for (int v : G[u]) {
        if (v == parent) continue;
        if (!disc[v]) {
            tarjanDFS(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) {

                blocks.emplace_back();
                while (true) {
                    int x = stk.back(); 
                    stk.pop_back();
                    inStack[x] = false;
                    blocks.back().push_back(x);
                    if (x == v) break;
                }

                blocks.back().push_back(u);
            }
        }
        else if (inStack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void dfsTree(int u, int parent, long long &totCircle) {
    visitedT[u] = true;

    subtree_size[u] = (u <= N ? 1LL : 0LL);

    for (int v : Tadj[u]) {
        if (v == parent) continue;
        if (!visitedT[v]) {
            dfsTree(v, u, totCircle);
            subtree_size[u] += subtree_size[v];

            long long a = subtree_size[v];
            long long b = (totCircle - subtree_size[v]);
            long long contrib = ( ( (weightT[u] % MOD + MOD ) % MOD ) 
                                * (a % MOD) % MOD 
                                * (b % MOD) ) % MOD;
            contrib = (2LL * contrib) % MOD;
            totalBad = (totalBad + contrib) % MOD;
        }
    }

}

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

    cin >> N >> M;
    G.assign(N+1, {});
    for (int i = 0, u, v; i < M; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    disc.assign(N+1, 0);
    low.assign(N+1, 0);
    inStack.assign(N+1, false);
    timerTarjan = 0;

    for (int u = 1; u <= N; u++){
        if (!disc[u]) {
            tarjanDFS(u, 0);

            if (!stk.empty()) {
                blocks.emplace_back();
                while (!stk.empty()) {
                    int x = stk.back();
                    stk.pop_back();
                    inStack[x] = false;
                    blocks.back().push_back(x);
                }
            }
        }
    }

    int B = (int)blocks.size();  

    Tadj.assign(N + B + 1, {});
    weightT.assign(N + B + 1, 0LL);

    for (int u = 1; u <= N; u++){
        weightT[u] = -1;
    }
    for (int i = 0; i < B; i++){
        int bnode = N + 1 + i;               
        long long blockSize = (long long)blocks[i].size();
        weightT[bnode] = (blockSize - 2LL);

        for (int v : blocks[i]) {
            Tadj[bnode].push_back(v);
            Tadj[v].push_back(bnode);
        }
    }

    int totalNodesT = N + B;
    visitedT.assign(totalNodesT+1, false);
    subtree_size.assign(totalNodesT+1, 0LL);

    for (int u = 1; u <= totalNodesT; u++){
        if (!visitedT[u] && ((u <= N && weightT[u] == -1) || (u > N && weightT[u] != 0))) {

            long long totCircle = 0;

            queue<int>q;
            vector<int>componentNodes;
            visitedT[u] = true;
            q.push(u);
            if (u <= N && weightT[u] == -1) totCircle++;
            componentNodes.push_back(u);

            while(!q.empty()){
                int x = q.front(); q.pop();
                for (int v : Tadj[x]) {
                    if (!visitedT[v]) {
                        visitedT[v] = true;
                        q.push(v);
                        componentNodes.push_back(v);
                        if (v <= N && weightT[v] == -1) {
                            totCircle++;
                        }
                    }
                }
            }

            for (int x : componentNodes) {
                visitedT[x] = false;
            }

            dfsTree(u, 0, totCircle);

            for (int x : componentNodes) {
                visitedT[x] = true;
            }
        }
    }

    long long totalOrdered = ( (long long)N * (N - 1) ) % MOD;
    totalOrdered = ( totalOrdered * (N - 2) ) % MOD;

    long long answer = ( (totalOrdered - totalBad) % MOD + MOD ) % MOD;
    cout << answer << "\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