#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const ll mxN = 1e5 + 5;
const ll mod = 1e9 + 7;
using namespace std;
struct edge{
int first,id,second;
};
vector<vector<edge>>v,tr;
int p[mxN];
int ans[mxN];
bool vis[mxN];
int dep[mxN];
void calctr(int u){
vis[u] = 1;
for(auto x : v[u]){
if(vis[x.F]) continue;
tr[x.F].push_back({u,x.id,!x.S});
tr[u].push_back(x);
calctr(x.F);
}
}
int n,m,pr;
int g[mxN],t[mxN];
int ng[mxN],nt[mxN];
set<int>s[mxN];
void merge(int a, int b){
if(s[a].size() < s[b].size()) swap(s[a],s[b]);
while(s[b].size()){
int u = *(s[b].begin());
if(g[u]){
if(s[a].find(g[u]) != s[a].end()) nt[a]--;
else ng[a]++;
}
if(t[u]){
if(s[a].find(t[u]) != s[a].end() )ng[a]--;
else nt[a]++;
}
s[a].insert(*(s[b].begin()));
s[b].erase(s[b].begin());
}
}
void dfs(int u,int par,int ty,int id){
dep[u] = dep[par] + 1;
for(auto x : tr[u]){
if(x.F == par) continue;
dfs(x.F,u,!x.S,x.id);
}
for(auto x : tr[u]){
if(x.F == par) continue;
merge(u,x.F);
}
if(g[u]){
if(s[u].find(g[u]) != s[u].end()) nt[u]--;
else ng[u]++;
}
if(t[u]){
if(s[u].find(t[u]) != s[u].end() )ng[u]--;
else nt[u]++;
}
s[u].insert(u);
ng[par] += ng[u];
nt[par] += nt[u];
if(p[u] == 0) p[u] = m;
int cnt = 0;
for(auto x : v[u]) {if(x.F != par || cnt) p[u] = min(dep[x.F],p[u]); else cnt++;}
// cout<<u<<' '<<nt[u]<<' '<<ng[u]<<' '<<p[u]<<' '<<par<<'\n';
if(p[par] == 0) p[par] = m;
p[par] = min(p[u],p[par]);
// cout<<u<<' '<<p[u]<<'\n';
if(p[u] >= dep[u]){
if(ng[u]) ans[id] = ty + 1;
else if(nt[u]) ans[id] = (!ty) + 1;
}
}
signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
cin >>n>>m;
v.resize(n + 4);
tr.resize(n + 4);
for(int i = 1;i <= m;i++){
int x,y;
cin >>x>>y;
v[x].push_back({y,i, 0});
v[y].push_back({x,i, 1});
}
cin >>pr;
for(int i = 0;i < pr;i++){
int x,y;
cin >>x>>y;
g[x] = y;
t[y] = x;
}
for(int i = 1;i <= n;i++){
if(vis[i]) continue;
calctr(i);
dfs(i,0,0,0);
}
// for(int i = 1;i <= m;i++) cout<<ans[i]<<' ';
// cout<<'\n';
for(int i = 1;i <= m;i++) cout<<(ans[i] == 0 ? 'B' : (ans[i] == 1 ? 'R' : 'L'));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
