#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int low[DIMN],lvl[DIMN] , f[DIMN] , d[DIMN] , l[DIMN] , up[DIMN] , fth[20][DIMN];
int lg[DIMN] , 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;
fth[0][nod] = tata;
f[nod] = 1;
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]);
}
}
pair <int,int> lca (int n , int x , int y){
int dif , p2 , swapped = 0;
/// aducem pe ac nivel
if (lvl[x] < lvl[y]){
swapped = 1;
swap(x , y); /// x e mai jos
}
dif = lvl[x] - lvl[y] - 1;
/// stramosul dif al lui x
while (dif > 0 && x!=0){
x=fth[lg[dif]][x];
dif=dif-(1<<lg[dif]);
}
/// acum sunt pe acelasi nivel
if (fth[0][x] == y){ /// y era tatal lui x
if (!swapped)
return make_pair(x , -1);
else return make_pair(-1 , x);
}
if (dif != -1)
x = fth[0][x];
for (p2 = lg[n] ; p2>=0 ; p2--){
if (fth[p2][x] != fth[p2][y]){
x = fth[p2][x];
y = fth[p2][y];
}
}
if (!swapped)
return make_pair(x , y);
else return make_pair(y , x);
}
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 , int val){
// 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 , val);
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , val);
}
else {
update (x,up[l[y]] , val);
update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , val);
}
}
else {
return update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , val);
}
}
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
for (i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
int k = 1;
while ((1<<k)<=n){
for (i=1;i<=n;i++){
fth[k][i] = fth[k-1][fth[k-1][i]] ;
}
k++;
}
/// ai precalculat pe lca in log pt ca ti a fost lene sa faci cu query in o(1)
fscanf (fin,"%d",&p);
for (i=1;i<=p;i++){
fscanf (fin,"%d%d",&x,&y);
z = lca ( n , x, y );
/// update pe lant x , z cu 1 = RIGHT
/// update pe lant y , z cu -1 = LEFT
// printf ("%d %d\n\n",z.first,z.second);
if (-1 != z.first)
update (x , z.first , 1);
if (-1 != z.second)
update (y , z.second, -1);
}
/// 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:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<dfs_tree[nod].size();i++){
~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:52: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:64: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:181: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:183: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:244: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:246: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 |
10232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10232 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 5 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10492 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 8 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10232 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 5 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10492 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 8 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 11 |
Correct |
381 ms |
42872 KB |
Output is correct |
| 12 |
Correct |
402 ms |
45612 KB |
Output is correct |
| 13 |
Correct |
444 ms |
49508 KB |
Output is correct |
| 14 |
Incorrect |
504 ms |
54520 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10232 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10616 KB |
Output is correct |
| 5 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10492 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 8 |
Correct |
13 ms |
10616 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10488 KB |
Output is correct |
| 11 |
Correct |
381 ms |
42872 KB |
Output is correct |
| 12 |
Correct |
402 ms |
45612 KB |
Output is correct |
| 13 |
Correct |
444 ms |
49508 KB |
Output is correct |
| 14 |
Incorrect |
504 ms |
54520 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
