Submission #309510

#TimeUsernameProblemLanguageResultExecution timeMemory
309510omletteOGLEDALA (COI15_ogledala)C++14
0 / 100
1 ms384 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...