#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef pair<int , int> ipair;
int n , m;
vector<ipair> adj[N] , G[N];
ipair edges[N];
int vis[N] , low[N] , disc[N] , bridges[N] , comp[N] , sum[N];
char ans[N];
map<ipair , int> mp;
int dtime = 0;
void dfs(int u , int p){
disc[u] = low[u] = dtime++; vis[u]=1;
for(ipair x : adj[u]){
int v = x.first , id = x.second;
if(v == p) continue;
if(!vis[v]){
dfs(v , u);
if(disc[u] < low[v]) bridges[id]=1;
low[u] = min(low[u] , low[v]);
} else low[u] = min(low[u] , disc[v]);
}
}
void component(int u , int x){
vis[u] = 1; comp[u] = x;
for(ipair X : adj[u]){
int v = X.first , id = X.second;
if(!vis[v] && !bridges[id]) component(v , x);
}
}
void go(int u , int p){
if(vis[u]) return;
vis[u]=1;
for(ipair x : G[u]){
int v = x.first , id = x.second;
if(v==p) continue;
go(v , u);
sum[u] += sum[v];
//cout << sum[u] << " sumu " << endl;
if(sum[v] > 0){
if(mp[{edges[id].first , edges[id].second}]) ans[id] = 'R'; else ans[id] = 'L';
}
if(sum[v] < 0){
if(mp[{edges[id].first , edges[id].second}]) ans[id] = 'L'; else ans[id] = 'R';
}
}
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u , v;
cin >> u >> v; --u; --v;
adj[u].emplace_back(v , i); adj[v].emplace_back(u , i);
edges[i].first = u;edges[i].second = v; mp[{u , v}]++;
}
memset(vis , 0 , sizeof(vis));
for(int i = 0; i < n; ++i){if(!vis[i]) dfs(i , -1);}
//for(int i = 0; i < m; ++i) if(bridges[i])cout <<i << " yes " << endl;
int c=0;
memset(vis , 0 , sizeof(vis));
for(int i = 0; i < n; ++i){
if(!vis[i]){component(i , c); c++;}
}
// cerr << c<< " C " << endl;
for(int i = 0; i < m; ++i){
int cu = comp[edges[i].first] , cv = comp[edges[i].second];
// cerr << cu << " cu " << cv << " cv " << endl;
if(bridges[i]){G[cu].emplace_back(cv , i); G[cv].emplace_back(cu , i);}
}
for(int i = 0; i < c; ++i){
// for(ipair v : G[i]) cout << v.first << " "; cerr << endl;
}
int p;
cin >> p;
while(p--){
int u , v; cin >> u >> v; --u; --v;
sum[comp[u]]++; sum[comp[v]]--;
// cout << comp[u] << "compu " << comp[v] << " compv " << endl;
// cout << sum[comp[v]] <<endl;
}
memset(vis , 0 , sizeof(vis));
for(int i = 0; i < c; ++i)go(i , -1);
for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
^~~
oneway.cpp:89:80: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
