Submission #716226

#	Time	Username	Problem	Language	Result	Execution time	Memory
716226		radal	Duathlon (APIO18_duathlon)	C++17	0 / 100	114 ms	27380 KiB

count_triplets

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 998244353;
constexpr int inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

int n,m;
vector<int> G[N];
vector<int> adj[N],cmp;
int h[N],mi[N]; 
int sz[N],par[N],deg[N];
int bl[N],sum[N],tot;
int cur;
bool vis[N],cut[N];
ll ans;

void add_ed(int u,int v){
	adj[u].pb(v);
	adj[v].pb(u);
	deg[u]++;
	deg[v]++;
}

void pre(int v,int p){
	cmp.pb(v);
	mi[v] = h[v];
	par[v] = p;
	for (int u : G[v]){
		if (h[u] == -1){
			h[u] = h[v]+1;
			pre(u,v);
			mi[v] = min(mi[v],mi[u]);
			if (mi[u] == h[v]) cut[v] = 1;
		}
		else{
			mi[v] = min(mi[v],h[u]);
		}
	}
}

void dfs(int v){
	vis[v] = 1;
	for (int u : G[v]){
		if (vis[u]) continue;
		if (mi[u] < h[v]){
			bl[u] = bl[v];
		}
		else{
			bl[u] = ++cur;
			sz[cur]++;
		}
		dfs(u);
	}
}

void calc(int v,int p){
	int s;
	if (v <= n) s = 1;
	else s = sz[v];
	sum[v] = s;
	for (int u : adj[v]){
		if (u != p){
			calc(u,v);
			sum[v] += sum[u]-1;
			if (v > n){
				ans -= 1ll*(sz[v]-1)*sum[u]*(sum[u]-1);
			}
			else{
//				ans -= 1ll*(sum[u]-sz[u])*(sum[u]-sz[u]-1);
			}
		}
	}
	if (p != -1){
		if (v > n)
			ans -= 1ll*(sz[v]-1)*(tot-sum[v])*(tot-sum[v]+1);
		else
			ans -= 1ll*(tot-(sum[v]+sz[p]-1))*(tot-(sum[v]+sz[p]-1)-1);
	}
}

int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	memset(h,-1,sizeof h);
	cin >> n >> m;
	rep(i,0,m){
		int u,v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	cur = n;
	rep(i,1,n+1){
		if (h[i] != -1) continue;
		cmp.clear();
		h[i] = 0;
		pre(i,-1);
		bl[i] = ++cur;
		dfs(i);
		tot = cmp.size();
		for (int v : cmp){
		   	sz[bl[v]]++;
			if (cut[v]){
				add_ed(bl[v],v);
			}
			if (v != i && mi[v]+1 == h[v]){
				add_ed(bl[v],par[v]);
			}
		}
		ans += 1ll*tot*(tot-1)*(tot-2);
		calc(i,-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