#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int low[DIMN],lvl[DIMN] , f[DIMN] , d[DIMN] , l[DIMN] , up[DIMN];
int poz[DIMN];
int lnt = 0;
map <pair <int,int> , int> mc , nr_mch;
pair <int,int> muchie[DIMN];
stack <int > st;
vector <int> v[DIMN] , w[DIMN] , dfs_tree[DIMN] , aint[DIMN];
int x;
void precalc (int nod){
int i,vecin;
d[nod]=1;
f[nod]=1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (!f[vecin]){
lvl[vecin]=1+lvl[nod];
dfs_tree[nod].push_back(vecin);
precalc (vecin);
d[nod]+=d[vecin];
}
}
}
void dfs_lant(int nod,int tata){
int i,vecin,ok=0,maxi,fiu;
f[nod] = 1;
//if (nod == 54)
// printf ("a");
maxi=0;
fiu=0;
for (i=0;i<dfs_tree[nod].size();i++){
vecin=dfs_tree[nod][i];
if (vecin != tata){
ok=1;
dfs_lant(vecin,nod);
if (d[vecin]>maxi){
maxi=d[vecin];
fiu=vecin;
}
}
}
if (!ok){ /// frunza
lnt++;
l[nod]=lnt; /// lantul din care apartine
w[lnt].push_back(nod);
}else { /// unim cu poz
w[l[fiu]].push_back(nod);
l[nod]=l[fiu];
for (i=0;i<dfs_tree[nod].size();i++){
vecin=dfs_tree[nod][i];
if (vecin!=tata && vecin!=fiu)
up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
}
}
}
void dfs_biconexe (int nod,int tt){
int i,vecin , nr = 0;
low[nod]=lvl[nod];
st.push(nod);
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin==tt)
continue;
if (lvl[vecin]==0){
lvl[vecin]=1+lvl[nod];
dfs_biconexe(vecin,nod);
low[nod]=min(low[nod],low[vecin]);
if (low[vecin]>=lvl[nod]){ /// nod e un nod critic
//mc[make_pair(nod,vecin)] = 1;
nr = 1;
do{
x=st.top();
st.pop();
nr++;
}
while (x!=vecin);
if (nr == 2){
mc[make_pair(nod,vecin)] = 1;
//printf ("%d %d\n" , nod, vecin);
}
/// am scos din stiva muchiile care sunt in subarborele nod->vecin
}
}
else low[nod]=min(low[nod],lvl[vecin]);
}
}
void update_aint (int lant , int nod , int st , int dr , int l , int r , int val){
int mid = (st + dr)/2;
//if ( l == 0 && r == 0 )
// printf ("%d %d\n",st,dr);
if (l <= st && dr <= r){
aint[lant][nod] = val; /// tot intervalul ala are aceeasi valoare (1 sau -1)
return;
}
if (l <= mid)
update_aint (lant , 2*nod , st , mid , l , r, val);
if (mid+1 <= r)
update_aint (lant , 2*nod+1 , mid+1 , dr , l , r, val);
}
void update (int x , int y){
// printf ("%d %d\n" , x , y );
if (l[x]!=l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]]){
update(up[l[x]] , y);
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , 1);
}
else {
update ( x , up[l[y]]);
update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , -1);
}
}
else {
if (lvl[x] < lvl[y]) /// x e lca ul , te duci in jos , pui -1
update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , -1);
else
update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , 1);
}
}
int query_aint (int lant,int nod,int st,int dr,int px){
int mid;
if (aint[lant][nod] !=0 || st == dr)
return aint[lant][nod];
mid=(st+dr)/2;
if (px<=mid)
return query_aint(lant,2*nod,st,mid,px);
else
return query_aint(lant,2*nod+1,mid+1,dr,px);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n, m , i , x , y , p , vecin , nod , sol;
pair <int,int> z;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
nr_mch[make_pair(x , y)]++;
nr_mch[make_pair(y , x)]++;
muchie[i] = make_pair(x , y);
}
for (i=1;i<=n;i++){
if (!lvl[i]){
lvl[i] = 1;
dfs_biconexe ( i, 0 );
}
}
/// vreau sa gasesc noduri critice
/// daca un drum intre X Y trece printr o mch critica ins ca
/// toate drumurile intre X Y trec pin acea muchie =>
/// muchia aia are sens prestabilit
for (i=1;i<=n;i++){
if (!f[i])
precalc(i);
}
memset (f , 0 , sizeof ( f ));
for (i=1;i<=n;i++){
if (!f[i])
dfs_lant(i , 0);
}
/// fiecare nod al catelea e
for (i=1;i<=lnt;i++){
reverse(w[i].begin(),w[i].end());
p=0;
for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){
/// pozitia lui din lantul curent
vecin=*j;
poz[vecin]=p;
p++;
}
}
/// folosesti aint
for (i=1;i<=lnt;i++)
aint[i].resize(w[i].size()*5);
/// ai precalculat pentru heavy
/// nu imi mai trb lca ul
fscanf (fin,"%d",&p);
for (i=1;i<=p;i++){
fscanf (fin,"%d%d",&x,&y);
/// update pe lant x , z cu 1 = RIGHT
/// update pe lant y , z cu -1 = LEFT
update (x , y);
}
/// am facut updateurile , e momentul sa fac queryurile
for (i=1;i<=m;i++){
if ( ( mc[muchie[i]] || mc[make_pair(muchie[i].second , muchie[i].first)] ) &&
nr_mch[muchie[i]] == 1 && muchie[i].first != muchie[i].second){
/// e muchie critica , trebuie sa vedem ce valoare are
if (mc[muchie[i]])
nod = muchie[i].second;
else nod = muchie[i].first;
sol = query_aint (l[nod] , 1 , 0 , w[l[nod]].size() - 1 , poz[nod]);
if (sol == 0)
fprintf (fout,"B");
else if (sol == -1){
if (nod == muchie[i].first)
fprintf (fout,"L");
else fprintf (fout,"R");
}
else {
if (nod == muchie[i].first)
fprintf (fout,"R");
else fprintf (fout,"L");
}
}
else fprintf (fout,"B");
}
return 0;
}
Compilation message
oneway.cpp: In function 'void precalc(int)':
oneway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_lant(int, int)':
oneway.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<dfs_tree[nod].size();i++){
~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<dfs_tree[nod].size();i++){
~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_biconexe(int, int)':
oneway.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&m);
~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:154:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:204:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&p);
~~~~~~~^~~~~~~~~~~~~
oneway.cpp:206:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10104 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10108 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
10488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10104 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10108 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
10488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10104 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10108 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
10488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
