oj.uz

답안 #110998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110998 2019-05-13T14:10:19 Z Pro_ktmr 철인 이종 경기 (APIO18_duathlon) C++14
0 / 100
 265 ms 40432 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);
	}
};

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;
int dfs(int now, int par, int idx){
	if(pre[now] != 0) return pre[now];
	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]);
		}
	}
}

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;
	dfs(0,-1,-1);
	uf.init(N);
	for(int i=0; i<N; i++) bfs(0);

	for(int i=1; i<N; i++) assert(pre[i] != 0);

	LL ans = N*(N-1)*(N-2);

	cout << ans << endl;
}

Compilation message

count_triplets.cpp: In function 'int dfs(int, int, int)':
count_triplets.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:62: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:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<edge[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 13056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 13056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 25056 KB Output is correct
2 Correct 251 ms 25712 KB Output is correct
3 Runtime error 246 ms 40432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 242 ms 16652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 265 ms 16764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 13056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 13056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -