Submission #250766

#	Time	Username	Problem	Language	Result	Execution time	Memory
250766		fivefourthreeone	Duathlon (APIO18_duathlon)	C++17	100 / 100	312 ms	38108 KiB

count_triplets

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 200001;
vector<int> adj[mxN];
vector<int> tree[mxN];
int cnt = 0;
bool flag[mxN];
int par[mxN], low[mxN], tin[mxN];
ll compsz[mxN];
ll sz[mxN];
int co = 0;
int n, m;
int totsz = 0;
vector<vector<ttgl>> fin;
vector<ttgl> st;
ll ans = 0;
void get(int u, bool root = 0) {
    tin[u]=low[u] = cnt++;
    int child = 0;
    for(int v: adj[u]) {
        if(v==par[u])continue;
        if(tin[v]==-1) {
            child++;
            par[v] = u;
            st.senpai({u, v});
            get(v);
            low[u] = min(low[v], low[u]);
            if((root&&child>1)||(!root&&tin[u]<=low[v])) {
                vector<ttgl> temp;
                while(st.back()!=(ttgl{u, v})) {
                    temp.senpai(st.back()); 
                    st.pop_back();
                }
                temp.senpai(st.back()); st.pop_back();
                fin.senpai(temp);
            }
        }else if(tin[v]<=tin[u]){
            low[u] = min(tin[v], low[u]);
            st.senpai({u, v});
        }
    }
}
void bcc() {
    memset(par, -1, sizeof(par));
    memset(low, -1, sizeof(low));
    memset(tin, -1, sizeof(tin));
    owo(i, 0, n) {
        if(tin[i]==-1) {
            get(i, 1);
            if(st.size()>0) {
                fin.senpai(st);
            }
            st.clear();
        }
    }
    for(auto a: fin) {
        set<int> s;
        for(auto b: a) {
            s.insert(b.first);s.insert(b.second);
        }
        compsz[co] = s.size();
        for(int k: s) {
            tree[k].senpai(n+co);
            tree[n+co].senpai(k);
        }
        co++;
    }
}
void dfssz(int u, int p) {
    flag[u] = true;
    sz[u] = u<n;
    for(int v: tree[u]) {
        if(v^p) {
            dfssz(v, u);
            sz[u]+=sz[v];
        }
    }
}
void solve(int u, int p, int rt) {
    if(u<n) {
        for(int v: tree[u]) {
            if(v^p) {
                ans-=(compsz[v-n]-1)*(sz[rt]-sz[v])*(sz[rt]-sz[v]-1);
            }else {
                ans-=(compsz[v-n]-1)*(sz[u]*(sz[u]-1));
            }
        }
    }
    for(int v: tree[u]) if(v^p) {
        solve(v, u, rt);
    }
}
int main()
{    
    //freopen("exercise.in", "r", stdin);
    //freopen("exercise.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    int a, b;
    owo(i, 0, m) {
        cin>>a>>b;
        a--; b--;
        adj[a].senpai(b);
        adj[b].senpai(a);
    }
    bcc();
    owo(i, 0, n) {
        if(!flag[i]) {
            dfssz(i, i);
            ans+=(sz[i]*(sz[i]-1)*(sz[i]-2));
            solve(i, i, i);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

• 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