Submission #403740

#	Time	Username	Problem	Language	Result	Execution time	Memory
403740		Bill_00	Duathlon (APIO18_duathlon)	C++14	0 / 100	245 ms	44228 KiB

count_triplets

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 100005
using namespace std;
ll n, m, timer, ans;
ll low[N], tin[N], p[N], sz[N], newsz[N];
vector<ll> adj[N], newadj[N];
unordered_map<ll, bool> bridge[N];
bool vis[N];
void dfs(ll v, ll p = -1) {
    vis[v] = 1;
    tin[v] = low[v] = timer++;
    for (ll to : adj[v]) {
        if(to == p) continue;
        if(vis[to]){
            low[v] = min(low[v], tin[to]);
        } 
        else{
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if(low[to] > tin[v]){
            	bridge[v][to]=1;
            	bridge[to][v]=1;
            }
        }
    }
}
void dfs1(ll node, ll head=1){
	sz[head]++;
	p[node]=head;
	vis[node]=1;
	for(ll to : adj[node]) {
		if(!vis[to]) {
			if(bridge[node][to]) {
				dfs1(to, to);
				newadj[head].pb(to);
				newadj[to].pb(head);
			}
			else dfs1(to, head);
		}
	}
}
void solve(ll node, ll par=-1){
	// cout << node << ' ' << sz[node] << '\n';
	ll sum=0, res=0;
	ans+=(sz[node]*(sz[node]-1)*(sz[node]-2));
	newsz[node]=sz[node];
	for(ll to : newadj[node]){
		if(par != to) {
			solve(to, node);
			newsz[node]+=newsz[to];
			sum+=newsz[to];
			res+=(newsz[to]*newsz[to]);
			ans+=((sz[node]-1)*(sz[node]-2)*newsz[to]*2+newsz[to]*(sz[node]-1)*2);
		}
	}
	ans+=((sz[node]-1)*(sz[node]-2)*(n-newsz[node])*2+(n-newsz[node])*(sz[node]-1)*2);
	ans+=((newsz[node]-sz[node])*(n-newsz[node])*2);
	ans+=(sum*sum-res); 
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	memset(vis,0,sizeof(vis));
	dfs1(1);
	solve(1);
	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