제출 #410090

#제출 시각아이디문제언어결과실행 시간메모리
410090errorgornDuathlon (APIO18_duathlon)C++17
100 / 100
110 ms24028 KiB
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...