Submission #771527

#TimeUsernameProblemLanguageResultExecution timeMemory
771527PoonYaPatOne-Way Streets (CEOI17_oneway)C++14
100 / 100
45 ms12844 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; typedef pair<int,int> pii; int n,m,mark1[100001],mark2[100001],dis[100001],k[100001]; vector<pii> adj[100001]; pii edge[100001]; bool vis[100001],use[100001]; string ans; void dfs(int x) { vis[x]=true; for (auto s : adj[x]) { if (use[s.second]) continue; use[s.second]=true; if (vis[s.first]) { ++mark2[x]; --mark2[s.first]; ans[s.second]='B'; } else { dfs(s.first); if (mark2[s.first]) ans[s.second]='B'; else { if (mark1[s.first]>0) { if (edge[s.second].first==x) ans[s.second]='L'; else ans[s.second]='R'; } else if (mark1[s.first]<0) { if (edge[s.second].first==x) ans[s.second]='R'; else ans[s.second]='L'; } else ans[s.second]='B'; } mark2[x]+=mark2[s.first]; mark1[x]+=mark1[s.first]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (int i=0; i<m; ++i) { int a,b; cin>>a>>b; ans+=" "; adj[a].push_back(pii(b,i)); adj[b].push_back(pii(a,i)); edge[i]=pii(a,b); } int k; cin>>k; while (k--) { int a,b; cin>>a>>b; mark1[a]++; mark1[b]--; } for (int i=1; i<=n; ++i) if (!vis[i]) dfs(i); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...