제출 #985898

#제출 시각아이디문제언어결과실행 시간메모리
985898alexddOne-Way Streets (CEOI17_oneway)C++17
60 / 100
3066 ms17072 KiB
#include<iostream> #include<vector> using namespace std; const int INF = 1e9; int n,m,p; pair<int,int> e[100005]; int xr[100005]; vector<int> con[100005]; vector<int> relatii[100005]; bool visited[100005],visited_init[100005]; int mind[100005][3];///1 - in sus int depth[100005]; int tin[100005],tout[100005],timer; char rez[100005]; int parent[100005]; void dfs_init(int nod) { visited_init[nod]=1; tin[nod]=++timer; for(auto x:con[nod]) { int adj = nod ^ xr[x]; if(!visited_init[adj]) { parent[adj]=nod; dfs_init(adj); } } tout[nod]=++timer; } bool isanc(int x, int y) { if(tin[x]<=tin[y] && tout[x]>=tout[y]) return 1; return 0; } void dfs(int nod, int par) { visited[nod]=1; mind[nod][0]=mind[nod][1]=mind[nod][2]=INF; for(auto x:con[nod]) { if(x==par) continue; int adj = nod ^ xr[x]; if(!visited[adj]) { depth[adj] = depth[nod]+1; dfs(adj,x); for(int i=0;i<3;i++) mind[nod][i] = min(mind[nod][i], mind[adj][i]); } else { rez[x] = 'B'; mind[nod][0] = min(mind[nod][0], depth[adj]); } } for(auto x:relatii[nod]) { if(x<0) { x = -x; mind[nod][2] = min(mind[nod][2], depth[x]); } else { mind[nod][1] = min(mind[nod][1], depth[x]); } } if(par==0) return; if(mind[nod][0] < depth[nod]) { rez[par] = 'B'; } else///bridge { if(mind[nod][1] >= depth[nod] && mind[nod][2] >= depth[nod]) rez[par] = 'B'; else { if(e[par].first==nod) { if(mind[nod][1] >= depth[nod]) rez[par] = 'R'; else rez[par] = 'L'; } else { if(mind[nod][1] >= depth[nod]) rez[par] = 'L'; else rez[par] = 'R'; } } //rez[par]='X'; } } int lca(int x, int y) { if(isanc(x,y)) return x; if(isanc(y,x)) return y; while(!isanc(x,y)) x=parent[x]; return x; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; int a,b; for(int i=1;i<=m;i++) { cin>>e[i].first>>e[i].second; con[e[i].first].push_back(i); con[e[i].second].push_back(i); xr[i] = e[i].first ^ e[i].second; } for(int i=1;i<=n;i++) if(!visited_init[i]) dfs_init(i); cin>>p; for(int i=1;i<=p;i++) { cin>>a>>b; int lc = lca(a,b); relatii[a].push_back(-lc); relatii[b].push_back(lc); } for(int i=1;i<=n;i++) if(!visited[i]) dfs(i,0); for(int i=1;i<=m;i++) cout<<rez[i]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...