Submission #309278

#	Time	Username	Problem	Language	Result	Execution time	Memory
309278		omlette	Mostovi (COI14_mostovi)	C++14	20 / 100	1094 ms	7288 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));
        while (it->first!=2*n+1 && it->first<n && it->second<y) {
            it++;
        }
        if (it->first<=n && follow(x,it->first)) {
            if (it->second>=y && follow(it->second,y)) {
                return true;
            }
        }
        return false;
    }
    else { //start on bottom
        it=brid.lower_bound(make_pair(x,0));
        if (it->first>x) it--;
        while (it->first!=0 && it->first>n && it->second>y) {
            it--;
        }
        if (it->first>n && follow(x,it->first)) {
            if (it->second<=y && follow(it->second,y)) {
                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;
        }
    }
}

• Subtask 1: 20 / 100