Submission #51103

#	Time	Username	Problem	Language	Result	Execution time	Memory
51103		Utaha	Duathlon (APIO18_duathlon)	C++14	71 / 100	373 ms	49100 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=200005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
vector<int> comp;
vector<int> child[maxn];
bool vis[maxn];

int tg[maxn];
int low[maxn];
int h[maxn];

vector<int> id[maxn];
int BCCpt=0;
vector<pii> q;
vector<int> curBCC;
int sz[maxn];

void dfs(int u,int t,int p,int H){
	comp.pb(u);
	vis[u]=1;
	tg[u]=t;
	low[u]=u;
	h[u]=H;
	for(int v:child[u]) if(v!=p){
		if(vis[v]){
			if(h[low[u]]>h[v]) low[u]=v;
		}
		else{
			q.pb(MP(u,v));
			dfs(v,t+1,u,H+1);
			if(h[low[u]]>h[low[v]]) low[u]=low[v];
			else{
				curBCC.clear();
				while(SZ(q)){
					pii tmp=q.back();
					curBCC.pb(tmp.F);
					curBCC.pb(tmp.S);
					q.pop_back();
					if(tmp==MP(u,v)) break;
				}
				SORT_UNIQUE(curBCC);
				for(int i:curBCC) id[i].pb(BCCpt);
				BCCpt++;
			}
		}
	}
}
vector<int> G[maxn];
ll ans=0;
bool bis[maxn];
int dfs(int u,bool isthin){
	bis[u]=1;
	int rem=SZ(comp)-sz[u];
	ll tt=(ll)rem*rem;
	ll sq=0;
	int cnt=0;
	for(int v:G[u]) if(!bis[v]){
		int tmp=dfs(v,!isthin);
		cnt++;
		rem-=tmp;
		tt-=(ll)tmp*tmp;
		sq+=(ll)tmp*tmp;
	}
	tt-=(ll) rem*rem;
	ans+=tt*sz[u];

	ans+=(ll)sz[u]*(sz[u]-1)*(SZ(comp)-sz[u])*2;
	ans+=(ll)sz[u]*(sz[u]-1)*(sz[u]-2);

	if(rem!=0){
		cnt++;
		sq+=(ll) rem*rem;
	}

	if(isthin){
		ll tmp=(ll)cnt*SZ(comp)*SZ(comp)-(ll)cnt*sq+2LL*sq-2LL*SZ(comp)*(SZ(comp)-sz[u])-(ll)cnt*sz[u];
		//cout<<u<<' '<<tmp<<'\n';
		ans+=tmp;
	}
	//cout<<u<<' '<<ans<<'\n';
	return SZ(comp)-rem;
}

int main()
{
	//IOS;
	int n;
	int m;
	cin>>n>>m;
	REP(i,m){
		int u,v;
		cin>>u>>v;
		u--;v--;
		child[u].pb(v);
		child[v].pb(u);
	}
	REP(x,n) if(!vis[x]){
		comp.clear();
		dfs(x,0,-1,0);
		/*for(int i:comp) cout<<low[i]<<" \n"[i==n-1];
		for(int i:comp){
			for(int j:id[i]) cout<<j<<' ';
			cout<<'\n';
		}*/
		REP(i,BCCpt) sz[i]=0;
		for(int i:comp){	
			if(SZ(id[i])==1){
				sz[id[i][0]]++;
			}
			else{
				int u=BCCpt++;
				for(int v:id[i]){
					G[u].pb(v);
					G[v].pb(u);
				}
				sz[u]=1;
			}
		}
		/*cout<<BCCpt<<'\n';
		REP(i,BCCpt){
			cout<<sz[i]<<'\n';
		}*/	

		dfs(0,1);
		REP(i,BCCpt){
			bis[i]=0;
			G[i].clear();
		}
		BCCpt=0;
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10