Submission #974665

#	Time	Username	Problem	Language	Result	Execution time	Memory
974665		efedmrlr	Duathlon (APIO18_duathlon)	C++17	100 / 100	96 ms	30300 KiB

count_triplets

#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e9 + 500;
int bcc = 1;
int tim = 0;
vector<int> tin(N, -1), low(N, 0);
vector<vector<int> > adj(N, vector<int>()), nadj(N, vector<int>());
vector<int> stck;
vector<int> sub(N, 0);
int n, m;
int cursz = 0;
lli ans = 0;
void dfs(int node, int par) {
    stck.pb(node);
    tin[node] = low[node] = tim++;
    cursz++;
    for(auto c : adj[node]) {
        if(c == par) {
            continue;
        }
        if(tin[c] != -1) {
            low[node] = min(low[node], tin[c]);
        }
        else {
            dfs(c, node);
            low[node] = min(low[node], low[c]);
            if(tin[node] <= low[c] ) {
                // cout << "artic:" << node << " \n";
                assert(stck.size());
                // cout << "bcc: ";
                while(!nadj[n + bcc].size() || nadj[n + bcc].back() != c) { // equavilant to pop until stck.back equals to c and then pop one more
                    // cout << stck.back() << " ";
                    nadj[n + bcc].pb(stck.back());
                    nadj[stck.back()].pb(n + bcc);
                    stck.pop_back();
                }
                assert(stck.size());
                nadj[n + bcc].pb(node);
                nadj[node].pb(n + bcc);
                // cout << node << " \n";
                // stck.pop_back();
                bcc++;
            }
        }
    }
}

void dfs2(int node, int par) {
    sub[node] = (node <= n);
    for(auto c : nadj[node]) {
        if(c == par) continue;
        dfs2(c, node);
        sub[node] += sub[c];
        if(node > n) {
            ans -= 1ll * sub[c] * (sub[c] - 1) * (nadj[node].size() - 1);
        }
    }
    if(node > n) {
        //for parent
        int sbt = cursz - sub[node];
        ans -= 1ll * sbt * (sbt - 1) * (nadj[node].size() - 1);
    }

}

void solve() {
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++) {
        if(tin[i] != -1) continue;
        cursz = 0;
        dfs(i, 0);
        ans += 1ll * cursz * (cursz - 1) * (cursz - 2);
        dfs2(i, 0);
    }
    cout << ans << "\n";
}


signed main() {
    fastio();
    solve();
}

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