#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 100000;
int N, M, P;
vector<int> gp[MAX_N+1];
vector<pii> edge;
vector<pii> edge2;
int num[MAX_N+1][2];
int cntn = 0;
int vst[MAX_N+1];
int p[MAX_N+1];
int up[MAX_N+1];
int lv[MAX_N+1];
bool chk[MAX_N+1];
void dfs(int x){
int cnt = 1;
vst[x] = true;
up[x] = lv[x];
num[x][0] = ++cntn;
for(int i=0; i<gp[x].size(); i++){
if(!vst[gp[x][i]]){
p[gp[x][i]] = x;
lv[gp[x][i]] = lv[x]+1;
dfs(gp[x][i]);
if(up[gp[x][i]]>lv[x]){
chk[gp[x][i]] = true;
}
up[x] = min(up[x], up[gp[x][i]]);
}else{
if(cnt>0 && gp[x][i]==p[x]) {
cnt--; continue;
}
up[x] = min(up[x], lv[gp[x][i]]);
}
}
num[x][1] = ++cntn;
}
struct SEG{
SEG(int l, int r, int mn, int mx) : l(l), r(r), mn(mn), mx(mx) {}
int l, r;
int mn, mx;
};
vector<SEG> seg1, seg2;
void init1(int idx, int s, int e){
if(s==e) return;
seg1[idx].l = seg1.size(); seg1.pb({-1, -1, INF, 0});
seg1[idx].r = seg1.size(); seg1.pb({-1, -1, INF, 0});
init1(seg1[idx].l, s, (s+e)/2);
init1(seg1[idx].r, (s+e)/2+1, e);
}
void init2(int idx, int s, int e){
if(s==e) return;
seg2[idx].l = seg2.size(); seg2.pb({-1, -1, INF, 0});
seg2[idx].r = seg2.size(); seg2.pb({-1, -1, INF, 0});
init2(seg2[idx].l, s, (s+e)/2);
init2(seg2[idx].r, (s+e)/2+1, e);
}
void u1(int idx, int s, int e, int x, int y){
seg1[idx].mn = min(seg1[idx].mn, y);
seg1[idx].mx = max(seg1[idx].mx, y);
if(s==e) return;
int m = (s+e)/2;
if(x<=m) u1(seg1[idx].l, s, m, x, y);
else u1(seg1[idx].r, m+1, e, x, y);
}
void u2(int idx, int s, int e, int x, int y){
seg2[idx].mn = min(seg2[idx].mn, y);
seg2[idx].mx = max(seg2[idx].mx, y);
if(s==e) return;
int m = (s+e)/2;
if(x<=m) u2(seg2[idx].l, s, m, x, y);
else u2(seg2[idx].r, m+1, e, x, y);
}
int mx1(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg1[idx].mx;
if(x>e || s>y) return 0;
return max(mx1(seg1[idx].l, s, (s+e)/2, x, y), mx1(seg1[idx].r, (s+e)/2+1, e, x, y));
}
int mn1(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg1[idx].mn;
if(x>e || s>y) return INF;
return min(mn1(seg1[idx].l, s, (s+e)/2, x, y), mn1(seg1[idx].r, (s+e)/2+1, e, x, y));
}
int mx2(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg2[idx].mx;
if(x>e || s>y) return 0;
return max(mx2(seg2[idx].l, s, (s+e)/2, x, y), mx2(seg2[idx].r, (s+e)/2+1, e, x, y));
}
int mn2(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg2[idx].mx;
if(x>e || s>y) return INF;
return min(mn2(seg2[idx].l, s, (s+e)/2, x, y), mn2(seg2[idx].r, (s+e)/2+1, e, x, y));
}
void update1(int x, int y){
u1(0, 1, cntn, x, y);
}
void update2(int x, int y){
u2(0, 1, cntn, x, y);
}
int max1(int x, int y){
return mx1(0, 1, cntn, x, y);
}
int min1(int x, int y){
return mn1(0, 1, cntn, x, y);
}
int max2(int x, int y){
return mx2(0, 1, cntn, x, y);
}
int min2(int x, int y){
return mn2(0, 1, cntn, x, y);
}
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<M; i++){
int x, y;
scanf("%d %d", &x, &y);
gp[x].pb(y); gp[y].pb(x);
edge.pb({x, y});
}
scanf("%d", &P);
for(int i=0; i<P; i++){
int x, y;
scanf("%d%d",&x, &y);
edge2.pb({x, y});
}
lv[1] = 1;
dfs(1);
seg1.pb({-1, -1, INF, 0}); seg2.pb({-1, -1, INF, 0});
init1(0, 1, cntn); init2(0, 1, cntn);
for(int i=0; i<P; i++){
update1(num[edge2[i].first][0], num[edge2[i].second][0]);
update2(num[edge2[i].second][0], num[edge2[i].first][0]);
}
for(int i=0; i<M; i++){
bool swp = false;
if(p[edge[i].first] = edge[i].second){
swp = true;
int tmp = edge[i].FI; edge[i].FI = edge[i].SE; edge[i].SE = tmp;
}
if(!chk[edge[i].second]){
printf("B");
continue;
}
int l = num[edge[i].second][0], r = num[edge[i].second][1];
if(max1(l, r)>r || min1(l, r)<l){
printf("%c", (swp?'R':'L'));
}else if(max2(l, r)>r || min2(l, r)<l){
printf("%c", (swp?'L':'R'));
}else{
printf("B");
}
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:177:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(p[edge[i].first] = edge[i].second){
~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P);
~~~~~^~~~~~~~~~
oneway.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x, &y);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
