#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],level[DIM],Size[DIM];
int viz[DIM],low[DIM],niv[DIM],b[DIM],E[DIM*3],first[DIM];
pair <int,int> rmq[20][DIM*3],mch[DIM];
vector <int> chains[DIM],L[DIM],edg[DIM],aint[DIM];
map < pair<int,int>, int > mch_critica;
deque <int> s;
int n,m,p,i,j,x,y,k,lca;
int nr_chains;
void dfs (int nod, int tata){
viz[nod] = 1;
low[nod] = niv[nod] = 1+niv[tata];
s.push_back (nod);
for (auto vecin:edg[nod]){
if (vecin == tata)
continue;
if (viz[vecin])
low[nod] = min (low[nod],niv[vecin]);
else {
dfs (vecin,nod);
low[nod] = min (low[nod],low[vecin]);
if (low[vecin] >= niv[nod]){
int x, cnt = 1;
do{
cnt++;
x = s.back();
s.pop_back();
} while (x != vecin);
if (cnt == 2){
/// am muchie critica
mch_critica[make_pair(nod,vecin)] = 1;
}}}}}
void build_tree (int nod, int tata){
viz[nod] = 1;
for (auto vecin:edg[nod]){
if (!viz[vecin]){
L[nod].push_back(vecin);
L[vecin].push_back(nod);
build_tree (vecin,nod);
}}}
void pre_dfs (int nod, int tata){
E[++k] = nod; /// parc. euler
first[nod] = k;
Size[nod] = 1;
level[nod] = 1 + level[tata];
int ok = 0;
for (auto vecin:L[nod]){
if (vecin == tata)
continue;
ok = 1;
pre_dfs (vecin,nod);
Size[nod] += Size[vecin];
E[++k] = nod;
}
if (!ok){ /// e frunza
nr_chains++;
chains[nr_chains].push_back(0);
chains[nr_chains].push_back(nod);
positionInChain[nod] = 1;
whatChain[nod] = nr_chains;
} else {
int maxim = 0, poz = 0;
for (auto vecin:L[nod]){
if (vecin == tata)
continue;
if (Size[vecin] > maxim){
maxim = Size[vecin];
poz = vecin;
}
}
chains[whatChain[poz]].push_back(nod);
positionInChain[nod] = chains[whatChain[poz]].size()-1;
whatChain[nod] = whatChain[poz];
/// chain father node
for (auto vecin:L[nod]){
if (vecin == tata || vecin == poz)
continue;
chainFatherNode[whatChain[vecin]] = nod;
}}}
int get_lca (int x, int y){
int pozx = first[x], pozy = first[y];
if (pozx > pozy)
swap (pozx,pozy);
int nr = b[pozy-pozx+1];
pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
return E[sol.second];
}
int query_aint (int chain, int nod, int st, int dr, int poz){
if (st == dr || aint[chain][nod])
return aint[chain][nod];
int mid = (st+dr)>>1;
if (poz <= mid)
query_aint (chain,nod<<1,st,mid,poz);
else query_aint (chain,(nod<<1)|1,mid+1,dr,poz);
}
void update_aint (int chain, int nod, int st, int dr, int x, int y, int val){
if (x <= st && dr <= y){
aint[chain][nod] = val;
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update_aint (chain,nod<<1,st,mid,x,y,val);
if (y > mid)
update_aint (chain,(nod<<1)|1,mid+1,dr,x,y,val);
}
void update_heavy (int x, int y, int val){
if (whatChain[x] == whatChain[y]){
int posx = positionInChain[x], posy = positionInChain[y];
if (posx > posy)
swap (posx,posy);
if (x == lca)
posx++;
if (y == lca)
posy--;
if (posx > posy)
return;
update_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy,val);
return;
}
if (level[chainFatherNode[whatChain[x]]] > level[chainFatherNode[whatChain[y]]]){
update_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,positionInChain[x],chains[whatChain[x]].size()-1,val);
int nr = chainFatherNode[whatChain[x]];
update_heavy (nr,y,val);
} else {
update_aint (whatChain[y],1,1,chains[whatChain[y]].size()-1,positionInChain[y],chains[whatChain[y]].size()-1,val);
int nr = chainFatherNode[whatChain[y]];
update_heavy (x,nr,val);
}}
int main (){
//ifstream fin ("date.in");
//ofstream fout ("date.out");
cin>>n>>m;
for (i=1;i<=m;i++){
cin>>x>>y;
edg[x].push_back(y);
edg[y].push_back(x);
mch[i] = make_pair (x,y);
}
/// trb sa gasesc muchiile critice, restul sigur fac parte dintr-un ciclu
/// deci sunt bidirectionale
for (i=1;i<=n;i++){
if (!viz[i]){
s.clear();
dfs (i,0);
}}
/// construiesc arborele
memset (viz,0,sizeof viz);
for (i=1;i<=n;i++){
if (!viz[i])
build_tree (i,0);
}
/// precalculare pt lca si heavy <3
for (i=1;i<=n;i++)
if (!level[i])
pre_dfs (i,0);
/// lca
for (int i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j+(1<<(i-1)) <= k && rmq[i-1][j+(1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j+(1<<(i-1))];
}
for (i=2;i<=k;i++)
b[i] = b[i/2] + 1;
for (i=1;i<=nr_chains;i++){
for (j=0;j<=4*chains[i].size();j++)
aint[i].push_back(0);
}
//for (i=1;i<=n;i++)
//fout<<positionInChain[i]<<" ";
cin>>p;
for (i=1;i<=p;i++){
cin>>x>>y;
lca = get_lca (x,y);
/// trb sa am grija sa nu dau update in lca
if (x != lca)
update_heavy (x,lca,1); /// 1 pt stanga - ma duc in sus
if (y != lca)
update_heavy (y,lca,2); /// 2 pt dreapta - ma duc in jos
/* if (i == 1){
fout<<query_aint (whatChain[5],1,1,chains[whatChain[5]].size()-1,positionInChain[5])<<endl;
fout<<query_aint (whatChain[4],1,1,chains[whatChain[4]].size()-1,positionInChain[4])<<endl;
}*/
}
for (i=1;i<=m;i++){
int x = mch[i].first, y = mch[i].second;
if (mch_critica[make_pair(x,y)] || mch_critica[make_pair(y,x)]){
int ok = 0;
if (level[x] < level[y]){
swap (x,y);
ok = 1;
}
int sol = query_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,positionInChain[x]);
if (sol == 0){
cout<<"B";
} else {
if (sol == 1){
if (!ok)
cout<<"R";
else cout<<"L";
} else {
if (!ok)
cout<<"L";
else cout<<"R";
}}
} else cout<<"B";
}
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:181:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j=0;j<=4*chains[i].size();j++)
~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int query_aint(int, int, int, int, int)':
oneway.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
13 ms |
10360 KB |
Output is correct |
| 3 |
Correct |
14 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
16 ms |
10744 KB |
Output is correct |
| 5 |
Correct |
18 ms |
10700 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10488 KB |
Output is correct |
| 7 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 8 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 9 |
Incorrect |
14 ms |
10488 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
13 ms |
10360 KB |
Output is correct |
| 3 |
Correct |
14 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
16 ms |
10744 KB |
Output is correct |
| 5 |
Correct |
18 ms |
10700 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10488 KB |
Output is correct |
| 7 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 8 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 9 |
Incorrect |
14 ms |
10488 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
13 ms |
10360 KB |
Output is correct |
| 3 |
Correct |
14 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
16 ms |
10744 KB |
Output is correct |
| 5 |
Correct |
18 ms |
10700 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10488 KB |
Output is correct |
| 7 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 8 |
Correct |
14 ms |
10744 KB |
Output is correct |
| 9 |
Incorrect |
14 ms |
10488 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
