#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 1e5 + 5, LOG = 17;
int n, m, p, tijme, low[MAXN], start[MAXN], anc[LOG][MAXN], sol[MAXN], dep[MAXN], deg[MAXN];
vector <point> E1[MAXN], E[MAXN];
bool bio[MAXN], bridge[MAXN];
point edge[MAXN];
void load(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
REP(i, m){
int a, b; cin >> a >> b; a --; b --;
E1[a].pb(point(b, i)); E1[b].pb(point(a, i));
edge[i] = point(a, b);
}
}
void dfsBridge(int x, int par = -1){
bio[x] = true;
start[x] = low[x] = tijme ++;
for(auto e : E1[x]){
if(e.first == par) continue;
if(bio[e.first])
low[x] = min(low[x], start[e.first]);
else{
dfsBridge(e.first, x);
low[x] = min(low[x], low[e.first]);
if(low[e.first] > start[x])
bridge[e.second] = true;
}
}
}
void findBridges(){
REP(i, n)
if(!bio[i])
dfsBridge(i);
}
int comp[MAXN];
void dfsGraph(int x, int color){
comp[x] = color;
bio[x] = true;
for(auto e : E1[x]){
if(bio[e.first]) continue;
if(bridge[e.second]){
E[color].pb(point(tijme + 1, e.second));
E[tijme + 1].pb(point(color, e.second));
dfsGraph(e.first, ++tijme);
}
else
dfsGraph(e.first, color);
}
}
void createGraph(){
memset(bio, 0, sizeof(bio));
tijme = -1;
REP(i, n)
if(!bio[i])
dfsGraph(i, ++tijme);
tijme ++;
/*REP(i, tijme){
sort(E[i].begin(), E[i].end());
E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());
}*/
}
vector <int> leaf;
void dfsLca(int x, int par = -1){
int cnt = 0;
bio[x] = true;
for(auto e : E[x]){
if(e.first == par) continue;
cnt ++;
dep[e.first] = dep[x] + 1;
anc[0][e.first] = x;
cout <<"veza " << x _ e.first << "\n";
dfsLca(e.first, x);
}
if(cnt == 0)
leaf.pb(x);
else
deg[x] = cnt;
}
void computeLca(){
memset(bio, 0, sizeof(bio));
REP(i, tijme)
if(!bio[i])
dfsLca(i);
FOR(i, 1, LOG) REP(j, tijme){
int x = anc[i - 1][j];
anc[i][j] = anc[i - 1][x];
}
}
int getLca(int x, int y){
if(x == y) return x;
if(dep[x] < dep[y]) swap(x, y);
for(int i = LOG - 1; i >= 0; --i)
if(dep[x] - (1 << i) >= dep[y])
x = anc[i][x];
if(x == y) return x;
for(int i = LOG - 1; i >= 0; --i){
if(anc[i][x] != anc[i][y]){
x = anc[i][x];
y = anc[i][y];
}
}
return anc[0][x];
}
vector <int> gdje[MAXN];
int suma[MAXN];
void solve(){
cin >> p;
REP(i, p){
int a, b; cin >> a >> b; a --; b --;
a = comp[a]; b = comp[b];
if( a == b ) continue;
cout << "comp " << a _ b << "\n";
int x = getLca(a, b);
if(a == x){
gdje[b].pb(-1);
gdje[x].pb(1);
//cout << b _ -1 _ x _ 1 << " ubacujem\n";
//cout << a _ b << " prvo\n";
}
else if(b == x){
gdje[a].pb(1);
gdje[x].pb(-1);
//cout << a _ b << " drugo\n";
}
else{
gdje[a].pb(1);
gdje[b].pb(-1);
//cout << a _ 1 _ b _ -1 << " ubacujem\n";
} // 1 dizem -1 spustam
}
queue <int> Q;
for(auto it : leaf)
Q.push(it);
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(auto it : gdje[x])
suma[x] += it;
//cout << suma[x] _ x << " suma i x\n";
for(auto e : E[x]){
if(deg[e.first] == 0) continue;
deg[e.first] --;
suma[e.first] += suma[x];
if(suma[x] > 0){
if(comp[edge[e.second].first] == x) sol[e.second] = 1;
else sol[e.second] = -1;
}
else if(suma[x] < 0){
if(comp[edge[e.second].first] == x) sol[e.second] = -1;
else sol[e.second] = 1;
}
if(deg[e.first] == 0)
Q.push(e.first);
}
}
REP(i, m){
if(sol[i] == -1) cout << 'L';
else if(sol[i] == 0) cout << 'B';
else if(sol[i] == 1) cout << 'R';
else assert(false);
}
}
int main(){
load();
findBridges();
createGraph();
computeLca();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
