Submission #1261049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261049		_rain_	Duathlon (APIO18_duathlon)	C++20	100 / 100	80 ms	37316 KiB

count_triplets

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(s) (int)(s).size()
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))

template<class X,class Y>
	bool maximize(X &x ,Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x ,Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
template<class X,class Y>
	Y Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 3e5;
const int M = (int) 2e5;
	int x[M + 2] , y[M + 2];
	int n , m;
	
LL f3(LL x){
	return x * (x - 1) * (x - 2) ;
}
	LL ans = 0;
	
	vector<int>ke[N + 2] , adj[N + 2] ;
		void add_canh(int u , int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
		
		int low[N + 2] = {} , num[N + 2] = {} , time_dfs = 0 ;
		int size_e = 0 , tot = 0;
		vector<int>order;
		
		void tarjan(int u , int p){
			order.push_back(u);
			++size_e;
			low[u] = num[u] = ++time_dfs;
			for(int v : ke[u]){
				if (v == p) continue;
				if (num[v]) minimize(low[u] , num[v]);
				else {
					tarjan(v , u);
					low[u] = min(low[u] , low[v]);
					if (low[v] >= num[u]){
						++tot;
						adj[u].push_back(n + tot);
						int tmp;
						do{
							tmp = order.back(); order.pop_back();
							adj[n + tot].push_back(tmp);
						}while (tmp != v);
					}
				}
			}
		} 
		
		LL sub[N + 2] = {};
		
		void dfs(int u , int p){
			sub[u] = (u <= n);
//			cout << u << ' ' << p << '\n';
			for(int& v : adj[u]) {
				if (v == p) continue;
				dfs(v , u);
				sub[u] += sub[v];
				if (u > n) ans -= (LL)(adj[u].size()) * sub[v] * (sub[v] - 1);
			}
			if (u > n) ans -= (LL)(adj[u].size()) * (size_e - sub[u]) * (size_e - sub[u] - 1);
			return;
		}
		
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	
			
		cin >> n >> m;
		for(int i = 1; i <= m; ++i){
			cin >> x[i] >> y[i];
			add_canh(x[i] , y[i]);
		}
		
		for(int i = 1; i <= n; ++i) if (!num[i]){
			size_e = 0;
			order.clear();
			tarjan(i,0);
			dfs(i,0);
			ans += f3(size_e);
		}
		cout << ans;
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:92:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:93:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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