Submission #886236

#	Time	Username	Problem	Language	Result	Execution time	Memory
886236		dwuy	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	4700 KiB

oneway

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;

struct SMT{
    int n;
    vector<pii> tree; /// {Min, Max}

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|1, {INF, -INF});
    }

    pii combine(pii a, pii b){
        return {min(a.fi, b.fi), max(a.se, b.se)};
    }

    void update(int pos, int val){
        int l = 1, r = n, id = 1;
        while(l<r){
            int mid = (l+r)>>1;
            if(pos<=mid) id <<= 1, r = mid;
            else l = mid + 1, id = id<<1|1;
        }
        if(val>=tree[id].fi && val<=tree[id].se) return;
        tree[id] = combine(tree[id], {val, val});
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    pii get(int l, int r, int id, const int &u, const int &v){
        if(l>v || r<u) return tree[0];
        if(l>=u && r<=v) return tree[id];
        int mid = (l+r)>>1;
        return combine(get(l, mid, id<<1, u, v), get(mid+1, r, id<<1|1, u, v));
    }

    pii get(int u, int v){
        return get(1, n, 1, u, v);
    }
};

struct DSU{
    int n;
    vector<int> e;

    DSU(int n=0){
        this->n = n;
        this->e.assign(n+5, -1);
    }

    int fp(int u){
        return e[u]<0? u : e[u] = fp(e[u]);
    }

    void unon(int u, int v){
        u = fp(u);
        v = fp(v);
        if(u==v) return;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }
};

const int MX = 100005;
int n, m, k, cnt = 0;
int num[MX]; /// open
int clo[MX]; /// close
int low[MX]; ///
bitset<MX> vist; /// visited edge
bitset<MX> isB; /// is bridge
pii edges[MX]; /// edges {u, v}
pii query[MX]; /// query {u, v}
vector<int> G[MX]; /// graph

void nhap(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        G[u].push_back(i);
        G[v].push_back(i);
    }
    cin >> k;
    for(int i=1; i<=k; i++){
        int u, v;
        cin >> u >> v;
        query[i] = {u, v};
    }
}

void tarjan(int u){
    num[u] = low[u] = ++cnt;
    for(int i: G[u]){
        if(vist[i]) continue;
        vist[i] = 1;
        int v = edges[i].fi^edges[i].se^u;
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v]>num[u]) isB[i] = 1;
        }
    }
    clo[u] = cnt;
}


void solve(){
    vist = 0; 
    for(int i=1; i<=n; i++) if(!num[i]) tarjan(i);
    SMT smt(n), rsmt(n);
    for(int i=1; i<=k; i++){
        int u, v;
        tie(u, v) = query[i];
        smt.update(num[u], num[v]);
        rsmt.update(num[v], num[u]);
    }
    string ans = "";
    for(int i=1; i<=m; i++){
        int u, v;
        tie(u, v) = edges[i];
        if(!isB[i]){
            ans += 'X';
            continue;
        }
        bool flag = 0;
        if(num[u] > num[v]) swap(u, v), flag = 1;
        pii r1 = smt.get(num[v], clo[v]);
        pii r2 = rsmt.get(num[v], clo[v]);
        assert(!((r1.fi < num[v] || r1.se > clo[v]) && (r2.fi < num[v] || r2.se > clo[v])));
        if(r2.fi < num[v] || r2.se > clo[v]) ans += flag? 'T':'P';
        else if(r1.fi < num[v] || r1.se > clo[v]) ans += flag? 'P':'T';
        else ans += 'B';
    }
    cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40