#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
