bzoj 2049[Sdoi 2008]동굴 탐사 LCT
8529 단어 LCT
http://www.lydsy.com/JudgeOnline/problem.php?id=2049
제목:
설명 휘 휘 휘 는 동굴 측량 에 열중한다.어느 날 그 는 지도 대로 JSZX 로 표 시 된 동굴 군 지역 을 찾 았 다.초보적인 측량 을 통 해 휘 휘 휘 는 이 구역 이 n 개의 동굴(각각 번호 가 1 에서 n)과 몇 개의 통로 로 구성 되 고 모든 통로 가 마침 두 개의 동굴 을 연결 한 것 을 발견 했다.만약 에 두 동굴 이 하나 또는 여러 개의 통 로 를 통 해 일정한 순서에 따라 연결 할 수 있다 면 이 두 동굴 은 연 결 된 것 이 고 순서대로 연 결 된 이 통 로 는 이 두 동굴 사이 의 경로 라 고 불 린 다.동굴 은 모두 매우 견고 하여 파괴 할 수 없 지만 통로 가 불안정 하고 외부 영향 으로 인해 자주 변화 한다.예 를 들 어 관련 기기 의 측정 결과 에 따 르 면 123 호 동굴 과 127 호 동굴 사이 에 가끔 통로 가 나타 나 고 가끔 이 통 로 는 어떤 기괴 한 원인 으로 파괴 된다.휘 휘 는 실시 간 으로 채널 의 모든 상황 을 휘 휘 휘 의 손 에 있 는 단말기 에 표시 할 수 있 는 모니터 가 있다.만약 에 동굴 u 와 동굴 v 사이 에 통로 가 나타 나 는 것 을 감지 하면 단말기 에 명령 이 나타 날 것 이다.Connect u v 는 동굴 u 와 동굴 v 간 의 통로 가 파괴 되 는 것 을 감지 하면단말기 에 Destroy u v 명령 이 나타 날 것 입 니 다.장기 적 으로 어렵 고 탁월 한 수공 추산 을 통 해 휘 휘 휘 는 이상 한 현상 을 발 견 했 습 니 다.통로 가 어떻게 바 뀌 든 지 간 에 임 의 시간 에 임 의 두 동굴 사이 에는 기껏해야 하나의 경로 만 있 습 니 다.그래서 휘 휘 휘 는 이것 이 어떤 본질 적 인 규칙 의 지배 로 인 한 것 이 라 고 굳 게 믿는다.그래서 휘 휘 휘 는 단말 기 를 지 키 기 전에 통로 의 변화 상황 을 통 해 이 본질 적 인 규칙 을 연구 하려 고 한다.그 러 던 어느 날,휘 휘 휘 는 산 더미 처럼 쌓 인 연산 지 에서 무 너 졌 습 니 다.................................................................휘 휘 휘 는 수시로 단말 기 를 통 해 Query u v 를 명령 하고 모니터 에 이때 동굴 u 와 동굴 v 가 연결 되 는 지 물 어보 고 싶 습 니 다.지금 너 는 그 를 위해 프로그램 을 만들어 서 매번 의 질문 에 대답 해 야 한다.첫 번 째 명령 이 표시 되 기 전에 JSZX 동굴 군 에는 채널 이 존재 하지 않 는 다 는 것 을 알 고 있 습 니 다.
Input 첫 번 째 행 위 는 두 개의 정수 n 과 m 로 동굴 의 개수 와 단말기 에 나타 난 명령 의 개 수 를 나타 낸다.아래 m 줄 은 단말기 에 나타 난 각 명령 을 차례대로 나타 낸다.각 줄 의 시작 은 명령 의 종 류 를 나타 내 는 문자열 s("Connect","Destroy"또는"Query"로 대소 문 자 를 구분 합 니 다)이 고 그 다음 에 두 개의 정수 u 와 v(1≤u,v≤n 및 u≠v)가 각각 두 동굴 의 번 호 를 표시 합 니 다.
출력 은 모든 Query 명령 에 대해 출력 동굴 u 와 동굴 v 가 서로 연결 되 는 지 여부 입 니 다.출력"Yes"입 니 다.그렇지 않 으 면 출력"No"입 니 다.(인용부 호 없 음)
샘플 입력 샘플 입력 1 cave.in 200 5 Query 123 127 Connect 123 127 Query 123 127 Destroy 127 123 123 Query 123 127 127
샘플 입력 2 cave.in 3 5 Connect 1 2 Connect 3 1 Query 2 3 Destroy 1 3 Query 2 3
생각:
엘 시 티 퀴즈.LCT 는 트 리 체인 과 어느 정도 유사 성 을 가지 고 있 습 니 다.그 다음 에 좀 더 복잡 해 졌 습 니 다.splay 로 유지 해 야 합 니 다.
#include
using namespace std;
const int N = 10000 + 10, INF = 0x3f3f3f3f;
int son[N][2], fat[N], siz[N], rev[N];
int top, stk[N];
bool is_root(int x)
{
return son[fat[x]][0] != x && son[fat[x]][1] != x;
}
void push_down(int x)
{
if(rev[x])
{
swap(son[x][0], son[x][1]);
rev[son[x][0]] ^= 1, rev[son[x][1]] ^= 1;
rev[x] ^= 1;
}
}
void Rotate(int x)// Rotate
{
int y = fat[x], p = son[y][0] == x;
son[y][!p] = son[x][p], fat[son[x][p]] = y;
if(! is_root(y)) son[fat[y]][son[fat[y]][1]==y] = x;
fat[x] = fat[y];
son[x][p] = y, fat[y] = x;
}
void splay(int x)
{
top = 0;
stk[++top] = x;
for(int i = x; !is_root(i); i = fat[i]) stk[++top] = fat[i];
for(int i = top; i >= 1; i--) push_down(stk[i]);
while(! is_root(x))
{
int y = fat[x], z = fat[y];
if(is_root(y)) Rotate(x);
else
{
if((x == son[y][0]) ^ (y == son[z][0])) Rotate(x), Rotate(x);
else Rotate(y), Rotate(x);
}
}
}
void access(int x)
{
int y = 0;
while(x)
{
splay(x);
son[x][1] = y;
y = x, x = fat[x];
}
}
void make_root(int x)
{
access(x); splay(x);
rev[x] ^= 1;
}
void cut(int x, int y)
{
make_root(x);
access(y); splay(y);
son[y][0] = 0, fat[x] = 0;
}
void link(int x, int y)
{
make_root(x); fat[x] = y; splay(x);
}
int find_root(int x)
{
while(son[x][0]) x = son[x][0];
return x;
}
// x , y access , x y
bool query(int x, int y)
{
make_root(x);
access(y); splay(y);
if(find_root(y) == x) return true;
else return false;
}
// splay
//int find_root(int x)
//{
// access(x); splay(x);
// while(son[x][0]) x = son[x][0];
// return x;
//}
//bool query(int x, int y)
//{
// return find_root(x) == find_root(y);
//}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
memset(fat, 0, sizeof fat);
char opt[10];
int x, y;
for(int i = 1; i <= m; i++)
{
scanf(" %s%d%d", opt, &x, &y);
if(opt[0] == 'C') link(x, y);
else if(opt[0] == 'D') cut(x, y);
else puts(query(x, y) ? "Yes" : "No");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ2049][SDOI2008]Cave동굴탐사LCT누드문제모형문제수조판수조, 적어도 현재 나는 수조만 쓰고 지침은 쓰지 않는다. LCT 같은 건 말 안 할 거야. 엉망진창이야. 어차피 이 편은 자용이야. 마찬가지로 이 블로그를 보는 사람들은 먼저 다른 곳에 가서 LCT를 배운 후에 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.