Submission #248540

#	Time	Username	Problem	Language	Result	Execution time	Memory
248540		maximath_1	Duathlon (APIO18_duathlon)	C++11	49 / 100	1087 ms	1048580 KiB

count_triplets

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

#define ll long long

int n, m, tin[100005], low[100005];
vector<int> adj[100005], adj_bcc[100005];
vector<int> euler_tour;
int bcc_id = 0, tim = 1, cnt = 0;
ll sz[200005], ans;

void dfs(int nw, int bf){
	tin[nw] = low[nw] = tim ++;
	euler_tour.push_back(nw);
	if(euler_tour.size() > 100069 * 2){
		cout << "do wa instead\n";
		exit(0);
	}
	cnt ++;

	for(int nx : adj[nw]) if(nx != bf){
//		cout << nx << " " << nw << " " << tin[nx] << " " << low[nx] << endl;
		if(tin[nx] == 0){
//			cout << "hi\n";
			dfs(nx, nw);
			low[nw] = min(low[nw], low[nx]);
			if(low[nx] >= tin[nw]){
				adj_bcc[nw].push_back(bcc_id);
				while(adj_bcc[bcc_id].empty() || adj_bcc[bcc_id].back() != nx){
					adj_bcc[bcc_id].push_back(euler_tour.back());
					euler_tour.pop_back();
				}
				bcc_id ++;
			}
		}else{
//			cout << "hey\n";
			low[nw] = min(low[nw], tin[nx]);
		}
	}
}

void exc(int nw){
	sz[nw] = (nw < n);
	for(int nx : adj_bcc[nw]){
		exc(nx);
		sz[nw] += sz[nx];
		if(nw >= n)
			ans -= sz[nx] * 1ll * (sz[nx] - 1) * 1ll * (ll)adj_bcc[nw].size();
	}

	if(nw >= n)
		ans -= (cnt - sz[nw]) * 1ll * (cnt - sz[nw] - 1) * 1ll * (ll)adj_bcc[nw].size();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(int u, v, i = 0; i < m; i ++){
		cin >> u >> v;
		u --; v --;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	bcc_id = n;
	for(int i = 0; i < n; i ++) if(tin[i] == 0){
		cnt = 0;
		dfs(i, -1);
		ans += cnt * 1ll * (cnt - 1) * 1ll * (cnt - 2);
		exc(i);
	}

	cout << ans << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 15 / 15
• Subtask 7: 0 / 20
• Subtask 8: 8 / 8
• Subtask 9: 0 / 10