Submission #347613

#TimeUsernameProblemLanguageResultExecution timeMemory
347613soroushOne-Way Streets (CEOI17_oneway)C++14
0 / 100
98 ms144236 KiB
/* #pragma GCC optimize("O2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,fma") //*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int , int> pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn = 3e6; const ll mod = 1e9+7; const ld PI = acos((ld)-1); #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} int n , m , p; vector < int > adj[maxn]; vector < pii > e; vector < pii > query; int par[maxn]; bool mark[maxn]; int h[maxn]; int up[maxn]; int getpar(int v){ return((v == par[v]) ? v : par[v] = getpar(par[v])); } void merge(int u, int v){ if((v = getpar(v)) == (u = getpar(u))) return; par[u] = v; } void dfs(int v , int p = 0){ mark[v] = 1; up[v] = h[v]; for(auto u : adj[v]) if(!mark[u]) h[u] = h[v] + 1, dfs(u , v), up[v] = min(up[v] , up[u]); else if (u!=p) up[v] = min(up[v] , h[u]); if(up[v] < h[v]) merge(v , p); } int prt[maxn]; vector < int > Adj[maxn]; int H[maxn]; void DFS(int v){ mark[v] = 1; for(auto u : Adj[v]) if(!mark[u]) H[u] = H[v] + 1, DFS(u) , prt[v] += prt[u]; } int32_t main(){ migmig; cin >> n >> m; for(int i = 1 ; i <= m ; i ++){ int u , v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); e.pb({u , v}); } cin >> p; for(int i = 0 ; i < p ; i ++){ int x , y; cin >> x >> y; query.pb({x , y}); } for(int i = 1 ; i <= n ; i ++) par[i] = i; for(int i = 1 ; i <= n ; i ++) if(!mark[i])dfs(i); for(int i = 0 ; i < p ; i ++){ int u = query[i].first; int v = query[i].second; if(getpar(u) == getpar(v))continue; prt[getpar(u)]++ , prt[getpar(v)]--; } for(int i = 0 ; i < m ; i ++){ int u = e[i].first; int v = e[i].second; if(getpar(u) == getpar(v))continue; Adj[getpar(u)].pb(getpar(v)); Adj[getpar(v)].pb(getpar(u)); } ms(mark , 0); for(int i = 1 ; i <= n ; i ++) if(!mark[getpar(i)])DFS(getpar(i)); for(auto uv : e){ if(getpar(uv.first) == getpar(uv.second)) cout << "B"; else{ int u = getpar(uv.first) , v = getpar(uv.second); if(H[u] > H[v]){ if(prt[u] == 0){ cout << "B"; continue; } if(prt[u] > 0) cout << "R"; else cout << "L"; } else{ if(prt[v] == 0){ cout << "B"; continue; } if(prt[v] > 0) cout << "R"; else cout << "L"; } } } return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...