Submission #1150717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150717		spycoderyt	Duathlon (APIO18_duathlon)	C++20	0 / 100	1099 ms	63944 KiB

count_triplets

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int timer = 0;
const int N = 1e6+5;
int vis[N],low[N],sz[N],st[N];
vector<int> A[N],t[N];
int bcci = 0,n,m,a,n2=0,b,ans=0,sti=0;
void dfs(int u,int par = -1) {
    n2++;
    vis[u] = low[u] = ++timer;
    st[sti++]=u;
    for(auto nxt : A[u])if(nxt!=par){
        if(vis[nxt])low[u]=min(low[u],vis[nxt]);
        else {
            dfs(nxt,u);
            low[u]=min(low[u],low[nxt]);
            if(low[nxt]>=vis[u]){
                t[u].push_back(bcci + n);
                while(t[bcci+n].empty() || t[bcci + n].back() != nxt) {
                    t[bcci + n].push_back(st[--sti]);
                }
                bcci++;
            }
        }
    }
}
void dfs2(int u,int par = -1) {
    sz[u] = u<n;
    for(auto nxt : t[u])if(nxt!=par){
        dfs2(nxt,u);
        sz[u]+=sz[nxt];
        if(u>=n)ans-=(t[u].size() - (par==-1)) * sz[nxt] * (sz[nxt]-1);
    }
    if(u>=n)ans-=(t[u].size())*(n2 - sz[u])*(n2 - sz[u]-1);
}
int32_t main() {
    cin>>n>>m;
    for(int i = 0;i<m;i++) {
        cin>>a>>b;a--,b--;
        A[a].push_back(b);A[b].push_back(a);
    }
    for(int i = 0;i<n;i++) {
        if(!vis[i])dfs(i);
        ans += n2 * (n2 - 1) * (n2 - 2);
        dfs2(i); // which will find the BCC and then do all the calculations 
        n2=0;
    }
    cout<<ans;
}

• 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