Submission #1258893

#TimeUsernameProblemLanguageResultExecution timeMemory
1258893dhuyyyyOne-Way Streets (CEOI17_oneway)C++20
0 / 100
3 ms5444 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; using ll = long long; using ii = pair<int,int>; using pii = pair<int,ii>; using aa = array<int,5>; const int N = 1e5+5; const int MAX = 100; const int INF = 1e9; const int MOD = 998244353; int n,m,u,v,q,cnt = 0,timer = 0; int num[N],low[N],scc[N],pre[N]; ii p[N]; bool vis[N]; stack<int> st; vector <int> adj[N],g[N]; map<ii,int> mp; void dfs(int u,int p){ num[u] = low[u] = ++timer; st.push(u); for(int v : adj[u]) { if (v == p) continue; if (!num[v]){ dfs(v,u); low[u] = min(low[u],low[v]); } else low[u] = min(low[u],num[v]); } if (low[u] == num[u]){ int v = -1; cnt++; while (v != u){ v = st.top(); scc[v] = cnt; st.pop(); } } } void dp(int u,int p){ vis[u] = 1; for (int it : g[u]){ if (vis[it]) continue; dp(it,u); pre[u] += pre[it]; } if (pre[u] > 0) mp[{u,p}] = 1; else if (pre[u] < 0) mp[{p,u}] = 1; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("main.in","r",stdin); // freopen("main.out","w",stdout); cin >> n >> m; for (int i = 1; i <= m; i++){ cin >> u >> v; p[i] = {u,v}; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++){ if (!num[i]) dfs(i,0); } for (int i = 1; i <= n; i++){ for (int x : adj[i]){ if (scc[i] == scc[x]) continue; g[scc[i]].push_back(scc[x]); } } cin >> q; for (int i = 1; i <= q; i++){ cin >> u >> v; pre[scc[u]]++; pre[scc[v]]--; } for (int i = 1; i <= cnt; i++){ if (!vis[i]) dp(i,0); } for (int i = 1; i <= m; i++){ tie(u,v) = p[i]; if (scc[u] == scc[v]){ cout << "B"; continue; } if (mp[{scc[u],scc[v]}]) cout << "R"; else if (mp[{scc[v],scc[u]}]) cout << "L"; else cout << "B"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...