Submission #543690

#	Time	Username	Problem	Language	Result	Execution time	Memory
543690		amunduzbaev	Duathlon (APIO18_duathlon)	C++17	100 / 100	161 ms	43532 KiB

count_triplets

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 4e5 + 5;
vector<int> edges[N], ee[N];
int tin[N], low[N], used[N];
int last, t;
vector<ar<int, 2>> ss;

void dfs(int u, int p = -1){
	tin[u] = low[u] = ++t;
	used[u] = 1;
	int c = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		if(used[x]){
			if(low[u] > tin[x]){
				low[u] = tin[x];
				ss.push_back({u, x});
			}
		} else { ++c;
			ss.push_back({u, x});
			dfs(x, u);
			low[u] = min(low[u], low[x]);
			
			if(p == -1 && c > 1){
				last++;
				while(ss.back() != (ar<int, 2>){u, x}){
					ee[ss.back()[0]].push_back(last);
					ee[ss.back()[1]].push_back(last);
					ss.pop_back();
				} ss.pop_back();
				ee[u].push_back(last);
				ee[x].push_back(last);
			}
			
			if(~p && low[x] >= tin[u]){
				last++;
				while(ss.back() != (ar<int, 2>){u, x}){
					ee[ss.back()[0]].push_back(last);
					ee[ss.back()[1]].push_back(last);
					ss.pop_back();
				} ss.pop_back();
				ee[u].push_back(last);
				ee[x].push_back(last);
			}
		}
	}
}

int sub[N], n, m;
long long res;

void dfs2(int u, int p = -1){
	//~ cout<<u<<endl;
	sub[u] = (u <= n);
	for(auto x : ee[u]){
		if(x == p) continue;
		dfs2(x, u);
		sub[u] += sub[x];
	}
}

int tot;
void dfs3(int u, int p = -1){
	used[u] = 1;
	if(u <= n){
		for(auto x : ee[u]){
			if(x == p) continue;
			dfs3(x, u);
		}
	} else {
		int sz = ee[u].size();
		assert(sz >= 2);
		for(auto x : ee[u]){
			if(x == p){
				res -= (tot - sub[u]) * 1ll * (tot - sub[u] - 1) * (sz - 1);
			} else {
				res -= sub[x] * 1ll * (sub[x] - 1) * (sz - 1);
				dfs3(x, u);
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 

	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	for(int i=1;i<=n;i++){
		if(used[i]) continue;
		dfs(i);
		last++;
		while(!ss.empty()){
			ee[ss.back()[0]].push_back(last);
			ee[ss.back()[1]].push_back(last);
			ss.pop_back();
		}
	}
	for(int i=1;i<=n;i++){
		sort(ee[i].begin(), ee[i].end());
		ee[i].erase(unique(ee[i].begin(), ee[i].end()), ee[i].end());
		for(auto& x : ee[i]){
			x += n;
			ee[x].push_back(i);
		}
	}
	//~ last += n;
	//~ for(int i=1;i<=n;i++){
		//~ for(auto x : ee[i]) cout<<i<<" "<<x<<"\n";
	//~ } cout<<last<<endl;
	
	memset(used, 0, sizeof used);
	for(int i=1;i<=n;i++){
		if(used[i]) continue;
		//~ cout<<i<<endl;
		dfs2(i);
		res += sub[i] * 1ll * (sub[i] - 1) * (sub[i] - 2);
		tot = sub[i];
		dfs3(i);
	}
	
	cout<<res<<"\n";
}

/*

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

*/

• 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