백준 : 개구리 점프: 17619번

 

https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

 

 

 

#include<bits/stdc++.h>

using namespace std;

typedef struct wood
{
	int x1, x2, y;
	int num;
}wd;


bool cmp(wd a, wd b)
{
	return a.x1 < b.x1;
}

int main(void)
{
	int n,q;
	int qus_1, qus_2;
	int now_group = 1;
	int group[100] = {0,};
	int max_x2=0;
	scanf("%d %d", &n, &q);

	vector<wd> v;
	wd temp;

	for(int i=1; i<=n; i++)	//입력.
	{
		temp.num = i;
		scanf("%d %d %d", &temp.x1, &temp.x2, &temp.y);
		v.push_back(temp);
	}

	sort(v.begin(), v.end(), cmp);	//x1의 순서로 정렬.

	for(int i=0; i<n; i++)
	{
	    group[v[i].num] = now_group;
        max_x2=v[i].x2;

        if(i==n-1)
        {
            break;
        }

        for(int j = i+1; max_x2>=v[j].x1; j++)
        {
            printf("=1.1= %d : %d\n", max_x2, v[j].x1);
            if(v[j].x2 > max_x2)
            {
                max_x2 = v[j].x2;
            }

            group[v[j].num] = now_group;
            i++;
            printf("=1.2= %d : %d\n", max_x2, v[j].x1);
        }
        now_group++;
	}



	for(int i = 0; i<=n; i++)
	{
		printf("=2=%d : %d\n", i, group[i]);
	}

	for(int i=0; i<q; i++)
	{
		scanf("%d %d", &qus_1, &qus_2);
		if(group[qus_1] == group[qus_2])	//같은 그룹이면 연결되어있다.
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}

	return 0;
}