글 읽기 - 반례를 구합니다

p_ce1052 3년 전 0

코드가 많이 깁니다만....주석에 전부 써놓았습니다 어느 부분이 잘못되었는지 / 또는 반례를 알고 싶습니다. 절단선과 절단점을 찾는 함수는 이미 다른 문제를 통해 검증했기 때문에 그 부분의 오류는 없을 것 같습니다

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>graph[100005];
int discovered[100005];
int reach[100005];
set<pi>cut_line;
set<int>cut_vertex;
int counter = 1;
int dp[100005][20];
int depth[100005];

int dfs(int cur,int p){
	discovered[cur] = counter++;
	int ret = discovered[cur];
	int child=0;
	for(int i=0; i<graph[cur].size(); i++){
		int nxt = graph[cur][i];
		if(!discovered[nxt]){
			int sub = dfs(nxt,cur);
			if(sub>discovered[cur]) cut_line.insert(pi(min(cur,nxt),max(cur,nxt)));
			ret = min(ret,sub);
			child++;
		}
		else if(nxt!=p) ret = min(ret,discovered[nxt]);
	}
	return ret;	
}
int dfs2(int cur){
	discovered[cur] = counter++;
	int ret = discovered[cur];
	int child = 0;
	for(int i=0; i<graph[cur].size(); i++){
		int nxt = graph[cur][i];
		if(!discovered[nxt]){
			child++;
			dp[nxt][0] = cur;
			depth[nxt] = depth[cur]+1;
			int sub = dfs2(nxt);
			if(discovered[cur]!=1 && sub>=discovered[cur]) cut_vertex.insert(cur);
			ret = min(ret,sub);
		}
		else ret = min(ret,discovered[nxt]);
	}
	if(discovered[cur]==1 && child>=2) cut_vertex.insert(cur);
	return reach[cur] = ret;
}
void init(int n){
	for(int j=1; j<20; j++){
		for(int i=1; i<=n; i++){
			dp[i][j] = dp[dp[i][j-1]][j-1];	
		}
	}
}
int f(int a,int b){
	if(depth[a]>depth[b]) swap(a,b); //a의 깊이가 더 깊다면 바꾼다.  
	int diff = depth[b]-depth[a];
	for(int i=0; diff; i++){
		if(diff%2) b = dp[b][i];
		diff/=2;
	}
	if(a!=b){
		for(int j=19; j>=0; j--){
			if(dp[a][j]!=dp[b][j]){
				a = dp[a][j];
				b = dp[b][j];
			}
		}
		a = dp[a][0];
		b = dp[b][0];
	}
	return a;
}
int f2(int a,int c){
	int diff = depth[a]-depth[c]; //c가 더 위에 있는 상황 
	diff--;
	for(int i=0; diff; i++){
		if(diff%2) a = dp[a][i];
		diff/=2;
	}
	return a;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m; 
	while(m--){
		int a,b;
		cin>>a>>b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1,0);
	counter = 1;
	memset(discovered,0,sizeof(discovered));
	dfs2(1);
	
	init(n); //lca테이블 초기화 
	int q;
	cin>>q;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			int a,b,g1,g2;
			cin>>a>>b>>g1>>g2;
			if(cut_line.find(pi(min(g1,g2),max(g1,g2)))!=cut_line.end()){ //절단선이라면 
				if(discovered[g1]>discovered[g2]) swap(g1,g2);
				if(discovered[a]<=discovered[g1] && discovered[b]<=discovered[g1]) cout<<"yes"<<'\n'; //둘다 g1보다 먼저 발견되었으면 경로 존재 
 				else if(discovered[a]>=discovered[g2] && discovered[b]>=discovered[g2]) cout<<"yes"<<'\n'; //둘다 g2보다 늦게 발견되었으면 경로 존재 
				else cout<<"no"<<'\n'; //절단선을 사이에 두고 있다면 경로 없음  
			}
			else cout<<"yes"<<'\n'; //절단선이 아니라면 당연히 경로 존재 
		}
		else{
			int a,b,c;
			cin>>a>>b>>c;
			if(cut_vertex.find(c)!=cut_vertex.end()){ //절단점이라면 
				if(a==c || b==c) cout<<"no"<<'\n'; //둘 중 하나가 c라면 무조건 불가능  
				else if(discovered[a]<discovered[c] && discovered[b]<discovered[c]) cout<<"yes"<<'\n'; //둘다 먼저 발견되었다면 가능 
				else{
					int a_c = f(a,c);
					int b_c = f(b,c);
					if(a_c==c && b_c==c){
						//둘 다 c에 속한다면 lca(a,b)를 확인
						if(f(a,b)==c){
							//두 서브트리에서 c위로 올라올 수 있는가 
							//c와 가장 가까운 a의 조상
							//c와 가장 가까운 b의 조상
							int aa = f2(a,c);
							int bb = f2(b,c);
							if(reach[aa]<discovered[c] && reach[bb]<discovered[c]) cout<<"yes"<<'\n';
							else cout<<"no"<<'\n'; 
						}
						else cout<<"yes"<<'\n'; //둘다 c에 속하는데 lca는 c가 아니라면 경로가 있다.  
					} 
					else if(a_c!=c && b_c!=c) cout<<"yes"<<'\n'; //둘 다 c의 서브트리가 아니므로 c를 잘라도 경로 존재
					else{ //하나가 c에 속해있다면 
						if(a_c!=c){ //b가 c에 속해있다.  
							int bb = f2(b,c);
							if(reach[bb]<discovered[c]) cout<<"yes"<<'\n';
							else cout<<"no"<<'\n';
						}
						else{ //a가 c에 속해있다.  
							int aa = f2(a,c);
							if(reach[aa]<discovered[c]) cout<<"yes"<<'\n';
							else cout<<"no"<<'\n';
						}
					} 
				}
			}
			else cout<<"yes"<<'\n'; //절단점이 아니라면 없애도 항상 경로 존재 
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 구합니다

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말