Submission #308026

#	Time	Username	Problem	Language	Result	Execution time	Memory
308026		qiangbao	Mostovi (COI14_mostovi)	C++98	100 / 100	409 ms	14456 KiB

mostovi

#include <iostream>
#include <set>

using namespace std;

typedef pair<int, int> pii;

int n, m;
set<int> block;
set<pii> bridge;
set<pii>:: iterator it1, it2, it3;

int x, y;

int diftp(int xx, int yy)
{
    if((xx<=n && yy>n) || (xx>n && yy<=n))
        return 1;
    return 0;
}

int wk1(int xx, int yy);
int wk2(int xx, int yy);
int wk3(int xx, int yy);

int wk1(int xx, int yy)
{
    if(*(block.lower_bound(xx))<yy)
        return 0;
    return 1;
}

int wk2(int xx, int yy)
{
    it3=bridge.lower_bound({xx, 0});
    if(it3->first==2*n+5 || diftp(it3->first, xx) || !wk1(xx, it3->first))
        return 0;
    
    if((yy<it3->second && wk3(it3->second, yy)) || (yy>=it3->second && wk1(it3->second, yy)))
        return 1;
    return 0;
}

int wk3(int xx, int yy)
{
    it1=bridge.lower_bound({xx, 0});
    it2=bridge.lower_bound({yy+1, 0}), it2--;
    if(it1->first==2*n+5 || diftp(it1->first, xx) || !wk1(xx, it1->first))
        return 0;
    if(it2->first==0 || diftp(it2->first, yy) || !wk1(it2->first, yy))
        return 0;
    
    if(wk1(it1->second, it2->second))
        return 1;
    return 0;
}

int main()
{
    ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int i;
    
    cin >> n >> m;
    
    block.insert(2*n+5);
    bridge.insert({0, 0});
    bridge.insert({2*n+5, 2*n+5});
    for(i=1;i<=m;i++){
        char com;
        cin >> com >> x >> y;
        if(x>n)
            x=2*n-x+n+1;
        if(y>n)
            y=2*n-y+n+1;
        if(com=='B'){
            block.insert(min(x, y));
        }
        else if(com=='A'){
            bridge.insert({x, y});
            bridge.insert({y, x});
        }
        else{
            if((x<=n && y<=n) || (x>n && y>n)){
                if(x<y){
                    if(wk1(x, y))
                        cout << "DA" << endl;
                    else
                        cout << "NE" << endl;
                }
                else{
                    if(wk3(x, y))
                        cout << "DA" << endl;
                    else
                        cout << "NE" << endl;
                }
            }
            else{
                if(wk2(x, y))
                    cout << "DA" << endl;
                else
                    cout << "NE" << endl;
            }
        }
    }
    
    return 0;
}

• Subtask 1: 100 / 100