Submission #732435

#	Time	Username	Problem	Language	Result	Execution time	Memory
732435		minhcool	Duathlon (APIO18_duathlon)	C++17	70 / 100	889 ms	19436 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define size sizee
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
/*
Ini algo: 
s, c, f is okay
- find the nearest arculation point from s->c
- erase that point
- check if c and f is the same component
*/
 
int n, m;
 
vector<int> Adj[N];
 
bool arcu[N];
int cnt, tim[N], low[N];
 
void dfs(int u, int p, int root){
	cnt++;
	tim[u] = low[u] = cnt;
	int child = 0;
	for(auto v : Adj[u]){
		if(!tim[v]){
			child++;
			dfs(v, u, root);
			low[u] = min(low[u], low[v]);
			if(u != root && low[v] >= tim[u]) arcu[u] = 1;
		}
		else low[u] = min(low[u], tim[v]);
	}
	if(u == root && child > 1) arcu[u] = 1;
//	cout << u << " " << arcu[u] << "\n";
}
 
bool vis[N];
int p[N];
 
ll ans = 0;
 
int where[3005][3005];
 
int ban;
bool viss[N];
void dfs(int u){
	viss[u] = 1;
	for(auto v : Adj[u]){
		if(viss[v] || v == ban) continue;
		dfs(v);
	}
}
 
int sz = 0, lst[N];
 
void dfs2(int u){
	sz++;
	vis[u] = 1;
	for(auto v : Adj[u]){
		if(vis[v]) continue;
		p[v] = u;
		dfs2(v);
	}
}
 
int tol[3005][3005];
 
void prep(int u, int root, int cnt){
	tol[root][cnt]++;
	where[root][u] = cnt;
	for(auto v : Adj[u]){
		if(v == root || where[root][v]) continue;
		prep(v, root, cnt);
	}
}
 
void solve_small(){
	for(int i = 1; i <= n; i++) if(!tim[i]) dfs(i, i, i);
	for(int i = 1; i <= n; i++){
		if(!arcu[i]) continue;
		int cnt = 0;
		for(auto it : Adj[i]){
			if(where[i][it]) continue;
			cnt++;
			prep(it, i, cnt);
		}
	}
	for(int s = 1; s <= n; s++){
		for(int i = 1; i <= n; i++) vis[i] = p[i] = 0;
		sz = 0;
		dfs2(s);
		for(int c = 1; c <= n; c++){
			if(!vis[c]) continue;
			if(c == s) continue;
			//vector<int> path;
			int cc = p[c];
			while(cc != s && where[cc][s] == where[cc][c]) cc = p[cc];
			if(!arcu[cc]){
				ban = -1;
				//cout << 1 << " " << sz << "\n";
				ans += sz - 2;
			//	for(int i = 1; i <= n; i++) viss[i] = 0;
			//	dfs(c);
			}
			else{
				ban = cc; 
				//cout << 2 << " " << tol[cc][where[cc][c]] << "\n";
				ans += tol[cc][where[cc][c]] - 1;
			//	for(int i = 1; i <= n; i++) viss[i] = 0;
			//	dfs(c);
			}
			//cout << s << " " << c << " " << ans << "\n";
		}
	}
}
 
ll size[N];
 
bool cyc = 0;
 
void dfss(int u, int p){
	size[u] = 1;
	for(auto v : Adj[u]){
		if(v == p || size[v]){
			if(size[v] && v != p) cyc = 1;
			continue;	
		}
		dfss(v, u);
		size[u] += size[v];
	}
}
 
void cal(int u, int p, int root){
	for(auto v : Adj[u]){
		if(v == p) continue;
		cal(v, u, root);
	}
	ll temp = size[root];
	for(auto v : Adj[u]){
		ll x = (v == p ? (size[u] - 1) : size[v]);
		ans += (temp - x - 1) * x;
	}
}
 
void process(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		Adj[x].pb(y);
		Adj[y].pb(x);
	}	
	if(n <= 1000) solve_small();
	else{
		for(int i = 1; i <= n; i++){
			if(size[i]) continue;
			cyc = 0;
			dfss(i, i);
			if(!cyc) cal(i, i, i);
			else{
				ans += (ll)size[i] * (ll)(size[i] - 1) * (ll)(size[i] - 2);
			}
		}
		//cout << ans << "\n";
	}
	//exit(0);
	//arc::process();
	cout << ans;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message (stderr)

count_triplets.cpp:17:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
count_triplets.cpp: In function 'void solve_small()':
count_triplets.cpp:103:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  103 |   for(int i = 1; i <= n; i++) vis[i] = p[i] = 0;
      |                                        ~~~~~^~~

• 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: 0 / 20
• Subtask 8: 8 / 8
• Subtask 9: 0 / 10