[BOJ] 16965 구간과 쿼리

Time Lapse :8min 3sec

16965.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int query, cmd, f, e;
vector<pair<int,int>> part;
void bfs(int f, int e) {
bool v[100] = {false, };
queue<int> q;
q.push(f);
v[f] = true;
while(!q.empty()) {
int p = q.front();
q.pop();
for(int i = 0; i < part.size(); i++) {
if(!v[i] && ((part[i].first < part[p].first && part[p].first < part[i].second) || (part[i].first < part[p].second && part[p].second < part[i].second))) {
v[i] = true;
q.push(i);
if(i == e) { printf("1\n"); return ; }
}
}
}
printf("0\n");
return;
}
int main(void) {
scanf("%d", &query);
for(int i = 0; i < query; i++) {
scanf("%d %d %d", &cmd, &f, &e);
switch (cmd) {
case 1: part.push_back(make_pair(f, e)); break;
case 2: bfs(f-1, e-1); break;
}
}
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/08/26/PS/BOJ/16965/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.