제출 #1027554

#제출 시각아이디문제언어결과실행 시간메모리
1027554vjudge1One-Way Streets (CEOI17_oneway)C++17
100 / 100
69 ms43856 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") #define ll long long #define pb push_back #define eb emplace_back #define pu push #define ins insert #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ff(x,a,b,c) for (auto x=a;x<=b;x+=c) #define fd(x,a,b,c) for (auto x=a;x>=b;x-=c) #define int ll using namespace std; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int, int> ii; const int N = 2e5+5; const int mod = 1e9+7; const int INF = 1e18; using cd = complex<double>; const long double PI = acos(-1); int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} int n,m,p,curtime = 0,cnt = 0; vector<pair<int,int>> adj[N],tree[N]; int num[N],low[N],idx[N],vis[N],a[N],b[N]; pair<int,int> edge[N]; vector<int> dir[N]; stack<int> st; bool check[N]; char ans[N]; void dfs1(int u,int p) { num[u] = low[u] = ++curtime; st.push(u); bool tmp = false; for (auto i : adj[u]) { int v = i.first; if (v==p && !tmp) {tmp = true; continue;} if (!num[v]) {dfs1(v,u); low[u] = min(low[u],low[v]);} else low[u] = min(low[u],num[v]); } if (low[u]==num[u]) { cnt++; int v; do { v = st.top(); st.pop(); idx[v] = cnt; check[v] = true; } while (v!=u); } } void dfs2(int u,int id) { vis[u] = 1; for (auto i : tree[u]) { if (!vis[i.first]) { dfs2(i.first,i.second); a[u]+=a[i.first]; b[u]+=b[i.first]; } } if (a[u]==b[u]) ans[id] = 'B'; else if (a[u]>b[u]) { if(idx[edge[id].first]==u) ans[id]='R'; else ans[id]='L'; } else { if(idx[edge[id].first]==u) ans[id]='L'; else ans[id]='R'; } } void solve() { cin>>n>>m; for (int i=1;i<=m;i++) { int u,v; cin>>u>>v; edge[i] = {u,v}; adj[u].pb({v,i}); adj[v].pb({u,i}); } for (int i=1;i<=n;i++) if (!check[i]) dfs1(i,i); for (int u=1;u<=n;u++) { for (auto i : adj[u]) if (idx[u]!=idx[i.first]) tree[idx[u]].pb({idx[i.first],i.second}); } cin>>p; for (int i=1;i<=p;i++) { int u,v; cin>>u>>v; if (idx[u]==idx[v]) continue; a[idx[u]]++; b[idx[v]]++; } for (int i=1;i<=cnt;i++) if (!vis[i]) dfs2(i,0); for (int i=1;i<=m;i++) { if (!ans[i]) cout<<'B'; else cout<<ans[i]; } } signed main() { bruh //freopen("input.inp","r",stdin); //freopen("output.inp","w",stdout); int t = 1; //cin>>t; while (t--) { solve(); cout<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...