Submission #555970

#	Time	Username	Problem	Language	Result	Execution time	Memory
555970		SirCovidThe19th	Duathlon (APIO18_duathlon)	C++17	49 / 100	131 ms	34084 KiB

count_triplets

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

const int mx = 1e5 + 5;

int n, m, ti, bccID, tin[mx], low[mx]; long long ans, curN, sz[mx];
vector<int> adj[mx], bct[mx*2]; stack<int> stk;

void AP(int cur, int p = 0){
    tin[cur] = ++ti; low[cur] = 1e9; stk.push(cur); curN++;
    int c = 0;
    for (int nxt : adj[cur]) if (nxt != p){
        if (tin[nxt]) low[cur] = min(low[cur], tin[nxt]);
        else{
            AP(nxt, cur); c++;
            low[cur] = min(low[cur], low[nxt]);
            if (low[nxt] >= tin[cur]){
                bccID++; bct[cur].push_back(bccID + n);
                while (1){
                    int tp = stk.top(); stk.pop(); 
                    bct[bccID + n].push_back(tp); 
                    if (tp == nxt) break;
                }
            }
        }
    }
}
void dfs(int cur){
    sz[cur] = (cur <= n);
    for (int nxt : bct[cur]){
        dfs(nxt); sz[cur] += sz[nxt]; 
        if (cur > n) ans -= bct[cur].size() * sz[nxt] * (sz[nxt] - 1);
    }
    if (cur > n) ans -= bct[cur].size() * (curN - sz[cur]) * (curN - sz[cur] - 1);
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) if (!tin[i]){
        curN = 0; AP(i);
        ans += curN * (curN - 1) * (curN - 2);
        dfs(i);
    }
    cout<<ans<<"\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 15 / 15
• Subtask 7: 0 / 20
• Subtask 8: 8 / 8
• Subtask 9: 0 / 10