oj.uz

Submission #111487

# Submission time Handle Problem Language Result Execution time Memory
111487 2019-05-15T13:05:26 Z Pro_ktmr Duathlon (APIO18_duathlon) C++14
0 / 100
 302 ms 44076 KB 
#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] = true;
	while(!que.empty()){
		int now2 = que.front();
		que.pop();
		for(int i=0; i<edge[now2].size(); i++){
			if(!canUse[now][i]) continue;
			if(flg[edge[now2][i]]) continue;
			uf.unite(now, edge[now2][i]);
			flg[edge[now2][i]] = true;
			que.push(edge[now2][i]);
		}
	}
}

vector<int> newEdge[100000];
int newSize[100000];
int newPar[100000] = {};
int newDfs(int now, int par){
	if(newPar[now] != 0) return newSize[now];
	newPar[now] = par;
	newSize[now] = uf.culcSize(now);
	sort(newEdge[now].begin(), newEdge[now].end());
	newEdge[now].erase(unique(newEdge[now].begin(), newEdge[now].end()), newEdge[now].end());
	for(int i=0; i<newEdge[now].size(); i++){
		if(newEdge[now][i] == par) continue;
		newSize[now] += newDfs(newEdge[now][i], now);
	}
	return newSize[now];
}

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(i);
	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)].PB(uf.root(edge[i][j]));
				newEdge[uf.root(edge[i][j])].PB(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);
	}
	*/

	//部分木の大きさ計算
	for(int i=0; i<N; i++){
		if(fact.root(i) != i) continue;
		newDfs(i, -1);
	}

	//答えの計算
	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);
		}
	}
	for(int i=0; i<N; i++){
		if(uf.root(i) != i) continue;
		int sum = 0;
		for(int j=0; j<newEdge[i].size(); j++){
			int now = newEdge[i][j];
			if(now == newPar[i]) continue;
			else{
				ans -= uf.culcSize(i) * newSize[now] * (newSize[now]-1);
				sum += newSize[now];
			}
		}
		sum = fact.culcSize(i) - sum - uf.culcSize(i);
		ans -= uf.culcSize(i) * sum * (sum-1);
	}
	
	cout << ans << endl;
}

Compilation message

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[now2].size(); i++){
                ~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int newDfs(int, int)':
count_triplets.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<newEdge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:134:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<edge[i].size(); i++){
                ~^~~~~~~~~~~~~~~
count_triplets.cpp:168:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<newEdge[i].size(); j++){
                ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8932 KB Output is correct
2 Correct 8 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Incorrect 9 ms 8960 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8932 KB Output is correct
2 Correct 8 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Incorrect 9 ms 8960 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 29308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 295 ms 43984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 9088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 302 ms 44076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8932 KB Output is correct
2 Correct 8 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Incorrect 9 ms 8960 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8932 KB Output is correct
2 Correct 8 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Incorrect 9 ms 8960 KB Output isn't correct
6 Halted 0 ms 0 KB -