CodeForces 566D(및 컬렉션 & 결합 구간)
6049 단어 함께 조사하여 모으다
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Even the most successful company can go through a crisis period when you have to make a hard decision — to restructure, discard and merge departments, fire employees and do other unpleasant stuff. Let’s consider the following model of a company.
There are n people working for the Large Software Company. Each person belongs to some department. Initially, each person works on his own project in his own department (thus, each company initially consists of n departments, one person in each).
However, harsh times have come to the company and the management had to hire a crisis manager who would rebuild the working process in order to boost efficiency. Let’s use team(person) to represent a team where person person works. A crisis manager can make decisions of two types:
At that the crisis manager can sometimes wonder whether employees x and y (1 ≤ x, y ≤ n) work at the same department.
Help the crisis manager and answer all of his queries.
Input
The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 500 000) — the number of the employees of the company and the number of queries the crisis manager has.
Next q lines contain the queries of the crisis manager. Each query looks like type x y, where . If type = 1 or type = 2, then the query represents the decision of a crisis manager about merging departments of the first and second types respectively. If type = 3, then your task is to determine whether employees x and y work at the same department. Note that x can be equal to y in the query of any type.
Output
For each question of type 3 print “YES” or “NO” (without the quotes), depending on whether the corresponding people work in the same department.
Examples
Input
Copy
8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7
Output
Copy
NO
YES
YES
n개 회사가 처음에는 모든 것이 독립된 m회 조작 1xy였다.x와 y를 2 x y로 합치기;x,x+1,,,,,y-1,y,모든 것을 3xy로 합치기;x, y가 한 집인지 물어보기;
관건은 조작2에 있다.만약 매번 x에서 y까지 모든 검사변을 폭력적으로 합병하면 시간이 초과됩니다.여기에 다른 사람의 블로그를 참고하여 오른쪽에 첫 번째 숫자에 속하지 않는 id를 저장합니다. 이렇게 하면 합병할 때 중복 검사를 하지 않고 합병되지 않은 위치로 바로 이동합니다.
#include
#include
#include
#include
using namespace std;
const int maxn = 200000+5;
int per[maxn];
int book[maxn];// id
int n,m,a,b,c;
int Find(int x)
{
int cx=x;
while(cx!=per[cx]){
cx=per[cx];
}
int i=x,j;
while(i!=cx){
j=per[i];
per[i]=cx;
i=j;
}
return cx;
}
void join(int x,int y)
{
int cx=Find(x),cy=Find(y);
if(cx!=cy){
per[cy]=cx;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
per[i]=i,book[i]=i+1;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a,&b,&c);
if(a==1){
join(b,c);
}
else if(a==2){
int to=0;
> for(int j=b+1;j<=c;j=to){
> join(j,j-1);
> to=book[j];
> book[j]=book[c];// , c
> }
}
else {
if(Find(b)==Find(c)) printf("YES
");
else printf("NO
");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2236 Wireless Network 간편한 검색 및 수집The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.