제출 #50055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50055		tmwilliamlin168	철인 이종 경기 (APIO18_duathlon)	C++14	100 / 100	283 ms	54416 KiB

count_triplets

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

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(ll x) {
	ll rev=x;
	int count = 0;
	if(x == 0) {
putchar_unlocked('0');
return;
}
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
}

const int mxN=1e5;
int n, m, dt=1, tin[mxN], low[mxN], sth, bccI, rt[2*mxN];
pii st[2*mxN];
ll sz1[2*mxN], sz2[mxN], ans;
vector<int> adj1[mxN], adj2[2*mxN];
set<int> bccs[mxN];
bool vis[2*mxN];

void dfs1(int u, int p) {
	tin[u]=low[u]=dt++;
	for(int v : adj1[u]) {
		if(!tin[v]) {
			int lsth=sth;
			st[sth++]={u, v};
			dfs1(v, u);
			low[u]=min(low[v], low[u]);
			if(low[v]>=tin[u]) {
				while(sth>lsth) {
					--sth;
					bccs[bccI].insert(st[sth].fi);
					bccs[bccI].insert(st[sth].se);
				}
				++bccI;
			}
		} else if(v!=p)
			low[u]=min(tin[v], low[u]);
	}
}

void dfs2(int u, int p) {
	sz1[u]=u<n;
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		rt[v]=rt[u];
		dfs2(v, u);
		sz1[u]+=sz1[v];
	}
}

void dfs3(int u, int p) {
	vis[u]=1;
	ll n2=sz1[rt[u]]-adj2[u].size();
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		dfs3(v, u);
		n2-=sz1[v]-1;
		if(u>=n)
			ans+=2*(sz1[v]-sz2[v]+adj2[u].size()-2)*(sz1[rt[u]]-adj2[u].size()-sz1[v]+1)+2*(adj2[u].size()-2)*(sz1[v]-1)*n2;
	}
	if(u<n) {
		n2=sz1[u]-sz2[u]+adj2[p].size()-2;
		for(int v : adj2[u]) {
			if(v==p)
				continue;
			n2-=sz1[v]-adj2[v].size()+1;
			ans+=2*(sz1[v]-adj2[v].size()+1)*n2;
		}
	}
}

int main() {
	n=in(), m=in();
	while(m--) {
		int u=in()-1, v=in()-1;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for(int i=0; i<n; ++i)
		if(!tin[i])
			dfs1(i, -1);
	for(int i=0; i<bccI; ++i) {
		for(int j : bccs[i]) {
			adj2[j].push_back(i+n);
			adj2[i+n].push_back(j);
			sz2[j]+=bccs[i].size()-1;
		}
	}
	for(int i=0; i<bccI; ++i) {
		ll bs=bccs[i].size();
		if(!rt[i+n]) {
			rt[i+n]=i+n;
			dfs2(i+n, -1);
		}
		ans+=bs*(bs-1)*(bs-2)+2*(bs-1)*(bs-1)*(sz1[rt[i+n]]-bs)+bs*(bs-1)*(bs-1);
	}
	for(int i=0; i<n; ++i)
		ans-=sz2[i]*sz2[i];
	for(int i=0; i<bccI; ++i)
		if(!vis[i+n])
			dfs3(i+n, -1);
	out(ans);
}

• 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