Submission #320206

#	Time	Username	Problem	Language	Result	Execution time	Memory
320206		Blagojce	Duathlon (APIO18_duathlon)	C++11	31 / 100	150 ms	24164 KiB

count_triplets

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 2e5+5;
mt19937 _rand(time(NULL));

int n, m;

vector<pii> g[mxn];
int l[mxn], r[mxn];
int d[mxn];
bool vis[mxn];
int mind[mxn];
bool bridge[mxn];

void dfs(int u, int p){
	vis[u] = true;
	for(auto e : g[u]){
		if(vis[e.st]){
			if(e.st != p) mind[u] = min(mind[u], d[e.st]);
			continue;
		}
		d[e.st] = d[u]+1;
		mind[e.st] = d[e.st];
		dfs(e.st, u);
		mind[u] = min(mind[u], mind[e.st]);
		if(mind[e.st] > d[u]){
			bridge[e.nd] = true;
		}
	}
}
ll sz[mxn];
int link[mxn];
ll gr;
void dfs2(int u){
	sz[gr]++;
	vis[u] = true;
	link[u] = gr;
	for(auto e : g[u]){
		if(vis[e.st] || bridge[e.nd]) continue;
		dfs2(e.st);
	}
}

vector<int> v[mxn];
ll sub[mxn];
ll ans = 0;
ll locn;
void dfs30(int u){
	locn += sz[u];
	vis[u] = true;
	for(auto e : v[u]){
		if(vis[e]) continue;
		dfs30(e);
	}
}

void dfs3(int u, int p){
	sub[u] = sz[u];
	ll s = 0;
	
	for(auto e : v[u]){
		if(e == p) continue;
		dfs3(e, u);
		sub[u] += sub[e];
		s += sub[e]*sub[e];
	}
	ll rem = locn-sub[u];
	s += rem*rem;
	
	ll all = locn-sz[u];
	
	ll temp = sz[u] * (all*all-s);
	ans += temp;
	ll temp2 = all*(sz[u]-1)*(sz[u]-2)+all*(sz[u]-1);
	ans += 2*temp2;
	
	
	ans += sz[u]*(sz[u]-1)*(sz[u]-2);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	fr(i, 0, m){
		cin >> l[i] >> r[i];
		--l[i], --r[i];
		g[l[i]].pb({r[i], i});
		g[r[i]].pb({l[i], i});
	}
	fr(i, 0, n) mind[i] = n;
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs(i, i);
	}	
	memset(vis, false, sizeof(vis));
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs2(i);
		++gr;
	}
	
	fr(i, 0, m){
		if(!bridge[i]) continue;
		int a = link[l[i]];
		int b = link[r[i]];
		v[a].pb(b);
		v[b].pb(a);
	}
	memset(vis, false, sizeof(vis));
	fr(i, 0, gr){
		if(vis[i]) continue;
		locn = 0;
		dfs30(i);
		dfs3(i, 0);
	
	}
	cout<<ans<<endl;
	
}

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