#include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
char ev;
set<pair<int,int> > brid;
set<pair<int,int> >::iterator it, it2;
set<int> noro;
bool follow (int x, int y) {
if ((x<=n && y<=n) || (x>n && y>n)) { //same side
if (x<=n && x<=y) { //top
if (*noro.lower_bound(x)<y) return false;
else return true;
}
else if (x>n && x>=y) { //bottom
if (*noro.upper_bound(y)<=x) return false;
else return true;
}
}
return false;
}
bool backward (int x, int y) {
if ((x<=n && y<=n) || (x>n && y>n)) { //same side
if (x<=n && x>=y) { //top
it=brid.lower_bound(make_pair(x,0));
it2=brid.lower_bound(make_pair(y,0));
if (it2->first>y) it2--;
if (it->first<=n && it2->first>0) {
if (follow(it->second, it2->second)) return true;
}
return false;
}
else if (x>n && x<=y) { //bottom
it=brid.lower_bound(make_pair(x,0));
if (it->first>x) it--;
it2=brid.lower_bound(make_pair(y,0));
if (it->first>n && it2->first!=2*n+1) {
if (follow(it->second, it2->second)) return true;
}
return false;
}
}
return false;
}
bool crossbrid (int x, int y) {
if (x<=n) { //start on top
it=brid.lower_bound(make_pair(x,0));
if (it->first<=n && follow(x,it->first)) {
if (it->second>=y && follow(it->second,y)) {
return true;
}
}
it=brid.lower_bound(make_pair(y,0));
if (it->first!=2*n+1 && follow(it->first,y)) {
if (it->second>=x && follow(x,it->second)) {
return true;
}
}
return false;
}
else { //start on bottom
it=brid.lower_bound(make_pair(x,0));
if (it->first>x) it--;
if (it->first>n && follow(x,it->first)) {
if (it->second<=y && follow(it->second,y)) {
return true;
}
}
it=brid.lower_bound(make_pair(y,0));
if (it->first>y) it--;
if (it->first!=0 && follow(it->first,y)) {
if (it->second>=x && follow(x,it->second)) {
return true;
}
}
return false;
}
}
bool reach(int x, int y) {
if (x<=n && y<=n) { //same side (top)
if (x<y) { //follow direction
return follow(x,y);
}
else { //against direction
return backward(x,y);
}
}
if (x>n && y>n) { //same side (bottom)
if (x>y) { //follow direction
return follow(x,y);
}
else { //against direction
return backward(x,y);
}
}
else { //different sides
return crossbrid(x,y);
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// ifstream cin(".in");
// ofstream cout(".out");
cin >> n >> m;
brid.insert(make_pair(0,0));
brid.insert(make_pair(2*n+1, 2*n+1));
noro.insert(2*n+1);
for (int event=1; event<=m; event++) {
cin >> ev >> a >> b;
if (ev=='A') {
brid.insert(make_pair(a,b));
brid.insert(make_pair(b,a));
}
else if (ev=='B') {
if (a<=n) noro.insert(min(a,b));
else (noro.insert(max(a,b)));
}
else {
if (reach(a,b)) cout << "DA" << endl;
else cout << "NE" << endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
