Submission #1213310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213310		spike1236	Duathlon (APIO18_duathlon)	C++20	0 / 100	65 ms	31676 KiB

count_triplets

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

static const int MOD = 1000000007;

int N, M;
vector<vector<int>> graphAdj;       

vector<int> disc, low, parentHT;
vector<bool> isCut;
int timerHT;
stack<pair<int,int>> edgeStack;
vector<vector<int>> blocks;  

void dfsHT(int u) {
    disc[u] = low[u] = ++timerHT;
    int childCount = 0;

    for (int v : graphAdj[u]) {
        if (disc[v] == 0) {

            parentHT[v] = u;
            childCount++;
            edgeStack.push({u, v});
            dfsHT(v);
            low[u] = min(low[u], low[v]);

            bool rootCase     = (parentHT[u] == 0 && childCount > 1);
            bool nonRootCase  = (parentHT[u] != 0 && low[v] >= disc[u]);
            if (rootCase || nonRootCase) {
                isCut[u] = true;

                vector<int> thisBlock;
                while (true) {
                    auto e = edgeStack.top();
                    edgeStack.pop();
                    thisBlock.push_back(e.first);
                    thisBlock.push_back(e.second);
                    if (e.first == u && e.second == v) break;
                }

                sort(thisBlock.begin(), thisBlock.end());
                thisBlock.erase(unique(thisBlock.begin(), thisBlock.end()), thisBlock.end());
                blocks.push_back(move(thisBlock));
            }
        }
        else if (v != parentHT[u] && disc[v] < disc[u]) {

            low[u] = min(low[u], disc[v]);
            edgeStack.push({u, v});
        }
    }
}

void findBiconnected() {
    disc .assign(N+1, 0);
    low  .assign(N+1, 0);
    parentHT .assign(N+1, 0);
    isCut .assign(N+1, false);
    timerHT = 0;

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

            if (!edgeStack.empty()) {
                vector<int> thisBlock;
                while (!edgeStack.empty()) {
                    auto e = edgeStack.top();
                    edgeStack.pop();
                    thisBlock.push_back(e.first);
                    thisBlock.push_back(e.second);
                }
                sort(thisBlock.begin(), thisBlock.end());
                thisBlock.erase(unique(thisBlock.begin(), thisBlock.end()), thisBlock.end());
                blocks.push_back(move(thisBlock));
            }
        }
    }
}

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

    cin >> N >> M;
    graphAdj.assign(N+1, {});

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

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

    int Tnodes = B + N + 1;  
    vector<vector<int>> Tadj(Tnodes);

    for(int i = 0; i < B; i++){

        for(int v : blocks[i]) {
            if (isCut[v]) {
                int blockNode = i+1;
                int cutNode   = B + v;
                Tadj[blockNode].push_back(cutNode);
                Tadj[cutNode].push_back(blockNode);
            }
        }
    }

    vector<long long> weight(Tnodes, 0LL);
    for(int i = 1; i <= B; i++){
        long long w = 0;
        for(int v : blocks[i-1]) {
            if (!isCut[v]) {
                w++;
            }
        }
        weight[i] = w;
    }
    for(int v = 1; v <= N; v++){
        if (isCut[v]) {
            weight[B + v] = 1;
        }
    }

    int root;
    if (B >= 1) {
        root = 1;
    } else {

        root = 1;
    }

    vector<int> parentT(Tnodes, 0);
    vector<long long> subtree_sz(Tnodes, 0LL);

    struct Item { int u, p, idx; };
    vector<Item> stk;
    stk.reserve(Tnodes * 2);
    stk.push_back({root, 0, 0});
    parentT[root] = 0;

    while(!stk.empty()) {
        Item &it = stk.back();
        int u = it.u;
        int p = it.p;
        int &idx = it.idx;
        if (idx < (int)Tadj[u].size()) {
            int v = Tadj[u][idx++];
            if (v == p) continue;
            parentT[v] = u;
            stk.push_back({v, u, 0});
        } else {

            long long sumw = weight[u];
            for (int v : Tadj[u]) {
                if (parentT[v] == u) {
                    sumw += subtree_sz[v];
                }
            }
            subtree_sz[u] = sumw;
            stk.pop_back();
        }
    }

    long long totalWeight = 0;
    for (int u = 1; u < Tnodes; u++) {
        totalWeight += weight[u];
    }

    long long totalBad = 0;
    for (int v = 1; v <= N; v++) {
        if (!isCut[v]) continue;
        int cutNode = B + v;
        long long szCutNode = subtree_sz[cutNode];  

        for (int blockNode : Tadj[cutNode]) {

            long long ai;
            if (parentT[blockNode] == cutNode) {

                ai = subtree_sz[blockNode];
            } else {

                ai = totalWeight - szCutNode;  
            }
            long long bi = (long long)blocks[blockNode - 1].size();

            long long term = ( (bi - 1) % MOD );
            long long x = ( (N - ai) % MOD + MOD ) % MOD;
            long long y = ( (N - ai - 1) % MOD + MOD ) % MOD;
            term = ( term * x ) % MOD;
            term = ( term * y ) % MOD;

            totalBad = ( totalBad + term ) % MOD;
        }
    }

    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