Submission #111258

#	Time	Username	Problem	Language	Result	Execution time	Memory
111258		Pro_ktmr	Duathlon (APIO18_duathlon)	C++14	0 / 100	333 ms	58620 KiB

count_triplets

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

//Union-Find木(サイズ有り)
struct UnionFind{
private:
	vector<int> parent;
	vector<int> size;
public:
	void init(int N){ //初期化する O(N)
		parent.clear();
		size.clear();
		for(int i=0; i<N; i++) parent.push_back(i);
		for(int i=0; i<N; i++) size.push_back(1);
	}
	int root(int a){ //親を返す O(log N)
		if(parent[a] == a) return a;
		return parent[a] = root(parent[a]);
	}
	void unite(int a, int b){ //木を併合する O(log N)
		int rootA = root(a);
		int rootB = root(b);
		if(rootA == rootB) return;
		if(size[rootA] < size[rootB]){
			parent[rootA] = rootB;
			size[rootB] += size[rootA];
			size[rootA] = 0;
		}
		else{
			parent[rootB] = rootA;
			size[rootA] += size[rootB];
			size[rootB] = 0;
		}
	}
	bool same(int a, int b){ //属する木が同じかを返す O(log N)
		return root(a) == root(b);
	}
	long long culcSize(int a){ //属する木の要素数を返す O(log N)
		return size[root(a)];
	}
	void decrement(int a, int x){
		a = root(a);
		size[a] -= x;
	}
};

LL N, M;
vector<int> edge[100000];
vector<bool> canUse[100000];
int sz[100000];

int pre[100000]={}, low[100000];
int c = 0;
vector<pair<int, int>> bridge;
UnionFind fact;
int dfs(int now, int par, int idx){
	if(pre[now] != 0) return pre[now];
	if(par != -1) fact.unite(now, par);
	pre[now] = c; c++;
	low[now] = pre[now];
	for(int i=0; i<edge[now].size(); i++){
		if(edge[now][i] == par) continue;
		low[now] = min(low[now], dfs(edge[now][i], now, i));
	}
	if(low[now] == pre[now] && par != -1){
		bridge.PB(MP(now, par));
		canUse[par][idx] = false;
		for(int i=0; i<edge[now].size(); i++)
			if(edge[now][i] == par) canUse[now][i] = false;
	}
	return low[now];
}

UnionFind uf;
bool flg[100000] ={};
void bfs(int now){
	if(flg[now]) return;
	queue<int> que;
	que.push(now);
	flg[now] = false;
	while(!que.empty()){
		int now = que.front();
		que.pop();
		for(int i=0; i<edge[now].size(); i++){
			if(!canUse[now][i]){

				continue;
			}
			if(flg[edge[now][i]]) continue;
			uf.unite(now, edge[now][i]);
			flg[edge[now][i]] = true;
			que.push(edge[now][i]);
		}
	}
}

set<int> newEdge[100000];

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		int a, b;
		cin >> a >> b;
		edge[a-1].PB(b-1);
		canUse[a-1].PB(true);
		edge[b-1].PB(a-1);
		canUse[b-1].PB(true);
	}
	for(int i=0; i<N; i++) sz[i] = edge[i].size();

	//橋の検出
	for(int i=0; i<N; i++) low[i] = INT_MAX;
	fact.init(N);
	for(int i=0; i<N; i++) dfs(i,-1,-1);

	//二重辺連結成分分解(オリジナル実装)
	uf.init(N);
	for(int i=0; i<N; i++) bfs(0);
	for(int i=0; i<N; i++){
		for(int j=0; j<edge[i].size(); i++){
			if(!uf.same(i, edge[i][j])){
				newEdge[uf.root(i)].insert(uf.root(edge[i][j]));
				newEdge[uf.root(edge[i][j])].insert(uf.root(i));
			}
		}
	}

	//葉の検出
	queue<int> que;
	for(int i=0; i<N; i++){
		if(uf.root(i) != i) continue;
		if(newEdge[i].size() == 1) que.push(i);
	}

	//答えの計算
	LL ans = 0;
	for(int i=0; i<N; i++){
		if(fact.root(i) == i){
			LL s = fact.culcSize(i);
			ans += s * (s-1) * (s-2);
		}
	}
	while(!que.empty()){
		int now = que.front();
		que.pop();
		if(newEdge[now].size() == 0) continue;
		LL tmp1 = fact.culcSize(now) - uf.culcSize(now);
		LL tmp2 = uf.culcSize(now);
		ans -= tmp1 * tmp2 * (tmp1-1);
		ans -= tmp2 * tmp1 * (tmp2-1);
		fact.decrement(now, uf.culcSize(now));
		int idx = *newEdge[now].begin();
		newEdge[now].erase(idx);
		newEdge[idx].erase(now);
		if(newEdge[idx].size() == 1) que.push(idx);
		//cout << now << " " << ans << endl;
	}
	cout << ans << endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int dfs(int, int, int)':
count_triplets.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<edge[now].size(); i++)
                ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void bfs(int)':
count_triplets.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<edge[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:123:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<edge[i].size(); i++){
                ~^~~~~~~~~~~~~~~

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