Submission #897791

#	Time	Username	Problem	Language	Result	Execution time	Memory
897791		Dec0Dedd	Duathlon (APIO18_duathlon)	C++14	100 / 100	127 ms	38720 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 3e5+10;

vector<int> G[N], NG[N];

int n, m, t=1, tin[N], low[N], rt[N], sz[N], cc=1;
bool vis[N];

ll tmp=0, ans=0;

vector<int> st;
void dfs(int v, int p=-1) {
    vis[v]=true;
    low[v]=tin[v]=t++;
    st.push_back(v);
    ++tmp;
    for (auto u : G[v]) {
        if (u == p) continue;
        if (vis[u]) low[v]=min(low[v], tin[u]);
        else {
            dfs(u, v);
            low[v]=min(low[v], low[u]);
            if (low[u] >= tin[v]) {
                NG[v].push_back(n+cc);
                while (NG[n+cc].empty() || NG[n+cc].back() != u) {
                    NG[n+cc].push_back(st.back()), st.pop_back();
                } ++cc;
            }
        }
    }
}

void solve(int v) {
    if (v <= n) sz[v]=1;
    else sz[v]=0;

    for (auto u : NG[v]) {
        solve(u); sz[v]+=sz[u];
        if (v > n) {
            ll sx=NG[v].size();
            ans-=sx*sz[u]*(sz[u]-1);
        }
    }

    if (v > n) {
        ll sx=NG[v].size();
        ans-=sx*(tmp-sz[v])*(tmp-sz[v]-1);
    }
}

void clear() {
    memset(vis, false, sizeof(vis));
}

int main() {
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int a, b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        tmp=0;
        dfs(i);
        ans+=tmp*(tmp-1)*(tmp-2);
        solve(i);
    } cout<<ans<<"\n";
}

• 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