#include<bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using aa = array<ll,5>;
const int N = 1e6;
const int INF = 1e9;
int p[100005];
vector<array<int,3>> bridge;
int timer=0;
int num[100005],low[100005];
vector<ii> adj[100005];
vector<int> adjtree[100005];
vector<ii> edge;
char ans[100005];
map<ii,bool> cb;
int par[100005][1];
int d[100005];
int pre[100005];
vector<int> mp[100005];
void dfs(int u,int pre) {
timer++;
num[u]=timer;
low[u]=num[u];
for(ii v:adj[u]) {
if(v.first==pre) continue;
if(!num[v.first] ) {
dfs(v.first,u);
low[u]=min(low[u],low[v.first]);
if(low[v.first]==num[v.first]) {
bridge.push_back({u,v.first,v.second});
cb[{u,v.first}]=1;
cb[{v.first,u}]=1;
}
}
else {
low[u]=min(low[u],num[v.first]);
}
}
return;
}
int get(int u) {
if(p[u]<0) return u;
return p[u]=get(p[u]);
}
void unite(int u,int v) {
u=get(u);
v=get(v);
if(u==v) return;
if(p[u]>p[v]) swap(u,v);
p[u]+=p[v];
p[v]=u;
return;
}
void tree(int u,int pre) {
mp[d[u]].push_back(u);
for(int v:adjtree[u]) {
v=get(v);
if(d[v]>0) continue;
par[v][0]=u;
d[v]=d[u]+1;
tree(v,u);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++) {
p[i]=-1;
}
for(int i=0;i<m;i++) {
int x,y;
cin >> x >> y;
adj[x].push_back({y,i});
adj[y].push_back({x,i});
edge.push_back({x,y});
ans[i]='X';
}
dfs(1,0);
for(ii e:edge) {
int u=e.fi;
int v=e.se;
if(cb[{u,v}]==0) {
unite(u,v);
}
}
for(array<int,3> e:bridge) {
int u=e[0];
int v=e[1];
u=get(u);
v=get(v);
adjtree[u].push_back(v);
adjtree[v].push_back(u);
}
for(int i=1;i<=n;i++) {
int u=get(i);
if(d[u]>0) continue;
//cout << u << ' ';
d[u]=1;
tree(u,0);
}
int k;
cin >> k;
for(int i=0;i<k;i++) {
int x,y;
cin >> x >> y;
x=get(x);
y=get(y);
pre[x]++;
pre[y]--;
}
for(int i=100000;i>0;i--) {
for(int u:mp[i]) {
int v=par[u][0];
//cout << u << ' ' << v << endl;
pre[v]+=pre[u];
}
}
for(array<int,3> e:bridge) {
int u=e[0];
int v=e[1];
u=get(u);
v=get(v);
if(d[u]<d[v]) swap(u,v);
if(pre[u]>0) {
if(u==edge[e[2]].first) {
ans[e[2]]='P';
}
else {
ans[e[2]]='T';
}
}
if(pre[u]<0) {
if(u==edge[e[2]].first) {
ans[e[2]]='T';
}
else {
ans[e[2]]='P';
}
}
}
for(int i=0;i<m;i++) {
cout << ans[i];
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
