#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=100010;
int N, M, K, cnt, dfsn[Nmax], G[Nmax], ans[Nmax], Dep[Nmax], Par[20][Nmax], X[Nmax], Y[Nmax];
bool chk[Nmax];
vector<pair<int, int>> adj[Nmax], adj2[Nmax];
stack<pair<int, int>> S;
map<pair<int, int>, bool> mp;
int Find(int x) {return G[x]?(G[x]=Find(G[x])):x;}
void Union(int u, int v) {
u=Find(u), v=Find(v);
if(u!=v) G[u]=v;
}
int DFS(int curr, int prev) {
dfsn[curr]=++cnt;
int ret=cnt;
for(auto [next, w]:adj[curr]) if(next!=prev) {
if(dfsn[next]<dfsn[curr]) S.push({curr, next});
if(dfsn[next]) ret=min(ret, dfsn[next]);
else {
int tmp=DFS(next, curr);
ret=min(ret, tmp);
if(tmp>=dfsn[curr]) {
bool flag=false;
while(!S.empty() && S.top()!=make_pair(curr, next)) {
Union(S.top().first, S.top().second);
S.pop();
flag=true;
}
if(flag) Union(S.top().first, S.top().second);
S.pop();
}
}
}
return ret;
}
void DFS2(int curr, int prev) {
chk[curr]=true;
for(auto [next, w]:adj2[curr]) if(next!=prev) {
Dep[next]=Dep[curr]+1, Par[0][next]=curr;
DFS2(next, curr);
}
}
int LCA(int u, int v) {
if(Dep[u]<Dep[v]) swap(u, v);
for(int i=19; i>=0; i--) if(Dep[Par[i][u]]>Dep[v]) u=Par[i][u];
if(Dep[u]!=Dep[v]) u=Par[0][u];
for(int i=19; i>=0; i--) if(Par[i][u]!=Par[i][v]) u=Par[i][u], v=Par[i][v];
if(u!=v) u=Par[0][u];
return u;
}
/*void Update(int s, int e) {
int l=LCA(s, e);
X[s]=-1, X[e]=1;
Y[l]++;
}*/
void Update(int s, int e) {
int l=LCA(s, e);
for(int i=s; i!=l; i=Par[0][i]) {
int j=Par[0][i], x=0;
for(auto [k, w]:adj2[j]) if(k==i) x=w;
if(x>0) ans[x]=-1;
else ans[-x]=1;
}
for(int i=e; i!=l; i=Par[0][i]) {
int j=Par[0][i], x=0;
for(auto [k, w]:adj2[j]) if(k==i) x=w;
if(x>0) ans[x]=1;
else ans[-x]=-1;
}
}
int DFS3(int curr, int prev) {
int a=0, b=0;
for(auto [next, w]:adj2[curr]) if(next!=prev) {
int tmp=DFS3(next, curr);
if(w*tmp>0) ans[abs(w)]=1;
if(w*tmp<0) ans[abs(w)]=-1;
if(tmp>0) a++;
else b++;
}
a-=Y[curr], b-=Y[curr];
if(a) return 1;
else if(b) return -1;
else return X[curr];
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(int i=1; i<=M; i++) {
int u, v; cin>>u>>v;
if(mp[{u, v}]) Union(u, v);
mp[{u, v}]=mp[{v, u}]=true;
adj[u].push_back({v, i}); adj[v].push_back({u, -i});
}
for(int i=1; i<=N; i++) if(!dfsn[i]) DFS(1, 0);
for(int i=1; i<=N; i++) {
for(auto [j, w]:adj[i]) {
int u=Find(i), v=Find(j);
if(u!=v) adj2[u].push_back({v, w});
}
}
for(int i=1; i<=N; i++)
sort(adj2[i].begin(), adj2[i].end()), adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
for(int i=1; i<=N; i++) if(!chk[i]) DFS2(i, 0);
for(int i=1; i<20; i++) for(int j=1; j<=N; j++) Par[i][j]=Par[i-1][Par[i-1][j]];
cin>>K;
while(K--) {
int s, e; cin>>s>>e;
s=Find(s), e=Find(e);
if(s!=e) Update(s, e);
}
// DFS3(1, 0);
for(int i=1; i<=M; i++) {
if(!ans[i]) cout<<"B";
else if(ans[i]>0) cout<<"R";
else cout<<"L";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
