Submission #232048

#	Time	Username	Problem	Language	Result	Execution time	Memory
232048		AQT	철인 이종 경기 (APIO18_duathlon)	C++14	10 / 100	151 ms	52620 KiB

count_triplets

// Problem : APIO '18 P3 - Duathlon
// Contest : DMOJ
// URL : https://dmoj.ca/problem/apio18p3
// Memory Limit : 1 MB
// Time Limit : 600 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> graph[100005], cgraph[200005];
vector<pair<int, int>> stk;
vector<vector<pair<int, int>>> cmp;
int par[200005], dfn[100005], low[100005], t;
long long sz[100005], dp[100005];
long long ans;

void dfs1(int n){
	low[n] = dfn[n] = ++t;
	int c = 0;
	for(int e : graph[n]){
		if(e == par[n]){
			continue;
		}
		if(!dfn[e]){
			c++;
			par[e] = n;
			stk.emplace_back(n, e);					
			dfs1(e);
			low[n] = min(low[n], low[e]);
			if((!par[n] && c >= 2) || (par[n] && low[n] == dfn[n])){
				pair<int, int> edg = {0, 0};
				vector<pair<int, int>> tmp;
				do{
					edg = stk.back();
					stk.pop_back();
					tmp.push_back(edg);
				}
				while(edg != make_pair(n, e));
				cmp.push_back(tmp);
			}
		}
		else if(dfn[e] < dfn[n]){
			low[n] = min(dfn[e], low[n]);
			stk.emplace_back(n, e);		
		}
	}
}

void dfs2(int n){
	sz[n] = n <= N;
	long long dsum = 0, cld = 0;
	for(int e : cgraph[n]){
		if(e != par[n]){
			cld++;
			par[e] = n;
			dfs2(e);
			if(n <= N){
				ans += dp[e] * sz[n];
				ans += sz[e] * (sz[n] - 1 + dsum);
				dsum += dp[e];
				dp[n] += dp[e] + sz[e];
				sz[n] += sz[e];
			}
			else{
				ans += dp[e] * sz[n];
				ans += sz[e] * dsum;
				dsum += dp[e];
				dp[n] += dp[e] + sz[e] * sz[n];				
				sz[n] += sz[e];
				//cout << n << " " << sz[e] << " " << sz[n] << " " << dp[e] << "\n";
			}
		}
	}
	//cout << n << " " << sz[n] << " " << dp[n] << "\n";
	/*
	if(n > N){
		dp[n] += cld * (cld-1) / 2;
	}
	*/
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i<=M; i++){
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	int C = N;
	for(int i = 1; i<=N; i++){
		if(!dfn[i]){
			dfs1(i);
			if(stk.size()){
				cmp.push_back(stk);
				stk.clear();
			}
			for(auto v : cmp){
				++C;
				for(auto p : v){
					cgraph[C].push_back(p.second);
					cgraph[C].push_back(p.first);
				}
				sort(cgraph[C].begin(), cgraph[C].end());
				cgraph[C].erase(unique(cgraph[C].begin(), cgraph[C].end()), cgraph[C].end());
				for(int n : cgraph[C]){
					cgraph[n].push_back(C);
				}
			}
			dfs2(i);
		}
	}
	cout << 2*ans << "\n";
}

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