Submission #1151295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151295		dpsaveslives	Duathlon (APIO18_duathlon)	C++20	100 / 100	82 ms	30020 KiB

count_triplets

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N,M;
const int MAXN = 2e5+5;
vector<int> adj[MAXN],adj2[MAXN];
int W[MAXN],num[MAXN],low[MAXN],st[MAXN],sz[MAXN];
int t,comps,nodes,top;
ll ans;
void tarjan(int u, int p){
    ++nodes;
    num[u] = low[u] = (++t);
    st[++top] = u;
    W[st[top]] = -1;
    for(auto v : adj[u]){
        if(v != p){
            if(!num[v]){
                tarjan(v,u);
                low[u] = min(low[u],low[v]);
                if(low[v] >= num[u]){
                    ++comps;
                    adj2[comps].push_back(u); adj2[u].push_back(comps);
                    W[comps]++;
                    do{
                        adj2[comps].push_back(st[top]);
                        adj2[st[top]].push_back(comps);
                        W[comps]++;
                    }while(st[top--] != v);
                }
            }
            else{
                low[u] = min(low[u],num[v]);
            }
        }
    }
}
void dfs(int u, int p){
    st[u] = (u <= N);
    for(auto v : adj2[u]){
        if(v != p){
            dfs(v,u);
            ans += 2ll*st[u]*st[v]*W[u];
            st[u] += st[v];

        }
    }
    ans += 2ll*st[u]*(nodes-st[u])*W[u];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 0;i<M;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    comps = N;
    for(int i = 1;i<=N;++i){
        if(!num[i]){
            nodes = 0;
            tarjan(i,0);
            dfs(i,0);
        }
    }
    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