Submission #309533

#	Time	Username	Problem	Language	Result	Execution time	Memory
309533		omlette	Mostovi (COI14_mostovi)	C++14	10 / 100	425 ms	10104 KiB

mostovi

#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) return follow(x,y); //follow direction
        else return backward(x,y); //against direction
    }
    if (x>n && y>n) { //same side (bottom)
        if (x>y) return follow(x,y); //follow direction
        else return backward(x,y); //against direction
    }
    else return crossbrid(x,y); //different sides
    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;
        }
    }
}

• Subtask 1: 10 / 100