Submission #410090

#	Time	Username	Problem	Language	Result	Execution time	Memory
410090		errorgorn	Duathlon (APIO18_duathlon)	C++17	100 / 100	110 ms	24028 KiB

count_triplets

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;
vector<int> al[100005];
vector<int> cjk[200005];
int IDX;
int _TIME=1;
int SZ;

int in[100005];
int low[100005];
vector<int> stk;

void dfs_cjk(int i,int p){
	in[i]=low[i]=_TIME++;
	SZ++;
	stk.pub(i);
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		if (in[it]==0){
			dfs_cjk(it,i);
			low[i]=min(low[i],low[it]);
			
			if (low[it]>=in[i]){
				while (true){
					int curr=stk.back();
					stk.pob();
					
					cjk[IDX].pub(curr);
					if (curr==it) break;
				}
				cjk[i].pub(IDX);
				IDX++;
			}
		}
		else{
			low[i]=min(low[i],in[it]);
		}
	}
}

ll ans=0;

ll dfs_calc(int i){
	ll curr=SZ;
	
	for (auto &it:cjk[i]){
		ll temp=dfs_calc(it);
		curr-=temp;
		
		if (i<=n) ans+=2*temp*(curr-1);
		else ans+=2*temp*(sz(cjk[i])-1)*curr;
	}
	
	int ss=SZ-curr;
	if (i<=n) ss++;
	
	return ss;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	IDX=n+1;
	rep(x,1,n+1) if (in[x]==0){
		SZ=0;
		dfs_cjk(x,-1);
		dfs_calc(x);
	}
	
	cout<<ans<<endl;
}

• 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