Submission #1213299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213299		spike1236	Duathlon (APIO18_duathlon)	C++20	0 / 100	1096 ms	31660 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;

inline long long modMul(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}
inline long long modAdd(long long a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

long long choose3(long long n) {
    if (n < 3) return 0;

    long long x = ((n % MOD) * ((n - 1) % MOD)) % MOD;
    x = (x * ((n - 2) % MOD)) % MOD;

    return (x * 166666668LL) % MOD;
}

int N, M;
vector<vector<int>> adj;      
vector<int> disc, low, parent;
vector<bool> isCut;
int timerDFS;
stack<pair<int,int>> edgeStack; 

vector<vector<int>> biconnComp; 

vector<vector<int>> compVerts;

vector<vector<int>> blockCutAdj;  

int numComp; 
int cutOffset;

vector<vector<long long>> cutSubtreeSizes;

void dfsBCC(int u) {
    disc[u] = low[u] = ++timerDFS;
    int children = 0;
    for (int v : adj[u]) {
        if (disc[v] == 0) {
            parent[v] = u;
            children++;

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

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

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

                sort(thisComp.begin(), thisComp.end());
                thisComp.erase(unique(thisComp.begin(), thisComp.end()), thisComp.end());
                biconnComp.push_back(thisComp);
            }
        }
        else if (v != parent[u] && disc[v] < disc[u]) {

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

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

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

    disc.assign(N+1, 0);
    low.assign(N+1, 0);
    parent.assign(N+1, 0);
    isCut.assign(N+1, false);

    timerDFS = 0;

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

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

    numComp = (int)biconnComp.size();
    cutOffset = numComp;  

    blockCutAdj.assign(numComp + N + 5, {});
    for(int i = 0; i < numComp; i++){

        for(int v : biconnComp[i]){
            if (isCut[v]) {
                int blockNode = i + 1;
                int cutNode = cutOffset + v;
                blockCutAdj[blockNode].push_back(cutNode);
                blockCutAdj[cutNode].push_back(blockNode);
            }
        }
    }

    cutSubtreeSizes.assign(N+1, {});
    vector<bool> visitedBC(numComp + N + 5, false);

    for(int v = 1; v <= N; v++){
        if (!isCut[v]) continue;

        int cutNodeV = cutOffset + v;
        visitedBC[cutNodeV] = true;

        for(int blockNode : blockCutAdj[cutNodeV]){
            if (visitedBC[blockNode]) continue;

            long long subtreeCount = 0;
            stack<int> stk;
            stk.push(blockNode);
            visitedBC[blockNode] = true;

            while(!stk.empty()){
                int x = stk.top();
                stk.pop();
                if (x <= numComp) {

                    int compIdx = x - 1;

                    int countInComp = (int)biconnComp[compIdx].size();

                    if (binary_search(biconnComp[compIdx].begin(), biconnComp[compIdx].end(), v)) {
                        countInComp--;
                    }
                    subtreeCount += countInComp;
                } else {

                    int u = x - cutOffset;
                    subtreeCount += 1;
                }

                for(int y : blockCutAdj[x]){
                    if (!visitedBC[y]) {
                        visitedBC[y] = true;
                        stk.push(y);
                    }
                }
            }

            cutSubtreeSizes[v].push_back(subtreeCount);
        }

        queue<int> q;
        visitedBC[cutNodeV] = false;
        for(int blockNode : blockCutAdj[cutNodeV]) {
            if (visitedBC[blockNode]) {

                q.push(blockNode);
                visitedBC[blockNode] = false;
            }
        }
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int y : blockCutAdj[x]){
                if (visitedBC[y]) {
                    visitedBC[y] = false;
                    q.push(y);
                }
            }
        }
    }

    long long totalBad = 0;
    for(int v = 1; v <= N; v++){
        if (!isCut[v]) continue;
        auto &sizes = cutSubtreeSizes[v];
        long long sumSz = 0;
        for(auto &x : sizes) sumSz += x;
        long long rem = (long long)(N - 1) - sumSz;
        if (rem > 0) sizes.push_back(rem);

        int k = (int)sizes.size();

        for(int i = 0; i < k; i++){
            for(int j = i + 1; j < k; j++){
                long long s_i = sizes[i];
                long long s_j = sizes[j];
                long long others = (long long)(N - 1) - s_i - s_j;
                long long contrib = ((s_i % MOD) * (s_j % MOD)) % MOD;
                contrib = ( (contrib % MOD) * (others % MOD) ) % MOD;
                totalBad = (totalBad + contrib) % MOD;
            }
        }
    }

    long long totalTriples = choose3(N);
    long long answer = ( (totalTriples - 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