제출 #403755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403755		Bill_00	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	230 ms	43060 KiB

count_triplets

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 100005
using namespace std;
ll n, nn, m, timer, ans;
ll low[N], tin[N], p[N], sz[N], newsz[N], compsz[N];
vector<ll> adj[N], newadj[N];
unordered_map<ll, bool> bridge[N];
bool vis[N], mark[N];
void dfs(ll v, ll p = -1) {
    vis[v] = 1;
    tin[v] = low[v] = timer++;
    for (ll to : adj[v]) {
        if(to == p) continue;
        if(vis[to]){
            low[v] = min(low[v], tin[to]);
        } 
        else{
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if(low[to] > tin[v]){
            	bridge[v][to]=1;
            	bridge[to][v]=1;
            }
        }
    }
}
void dfs1(ll node, ll head){
	nn++;
	sz[head]++;
	p[node]=head;
	vis[node]=1;
	for(ll to : adj[node]) {
		if(!vis[to]) {
			if(bridge[node][to]) {
				dfs1(to, to);
				newadj[head].pb(to);
				newadj[to].pb(head);
			}
			else dfs1(to, head);
		}
	}
}
void solve(ll node, ll par=-1){
	// cout << node << ' ' << sz[node] << '\n';
	vis[node]=1;
	ll sum=0, res=0;
	ans+=(sz[node]*(sz[node]-1)*(sz[node]-2));
	newsz[node]=sz[node];
	for(ll to : newadj[node]){
		if(par != to) {
			solve(to, node);
			newsz[node]+=newsz[to];
			sum+=newsz[to];
			res+=(newsz[to]*newsz[to]);
			ans+=((sz[node]-1)*(sz[node]-2)*newsz[to]*2+newsz[to]*(sz[node]-1)*2);
		}
	}
	ans+=((sz[node]-1)*(sz[node]-2)*(nn-newsz[node])*2+(nn-newsz[node])*(sz[node]-1)*2);
	ans+=((newsz[node]-sz[node])*(nn-newsz[node])*2);
	ans+=(sum*sum-res);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(ll i=1;i<=n;i++){
		if(vis[i]==0) dfs(i);
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(vis[i]==0){
			nn=0;
			dfs1(i,i);
			compsz[i]=nn;
			mark[i]=1;
		} 
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(mark[i]==1){
			nn=compsz[i];
			solve(i);
		}
	}
	cout << ans;
}	

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