Submission #696206

#TimeUsernameProblemLanguageResultExecution timeMemory
696206hamidh100One-Way Streets (CEOI17_oneway)C++17
100 / 100
182 ms28696 KiB
/* In the name of God */ #include <iostream> #include <iomanip> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <string> #include <string.h> #include <algorithm> #include <bitset> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <map> #include <numeric> #include <limits> #include <limits.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef map<int, int> MPII; typedef vector<int> VI; typedef vector<ll> VL; #define PB push_back #define POP pop_back #define MP make_pair #define all(a) (a).begin(), (a).end() #define SORT(a) sort(all(a)) #define REVERSE(a) reverse(all(a)) #define sep ' ' #define endl '\n' #define dbg(x) cerr << '[' << #x << ": " << x << "]\n" #define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n" #define Yes cout << "Yes\n" #define YES cout << "YES\n" #define No cout << "No\n" #define NO cout << "NO\n" #define OK cout << "OK\n" const ll INF = (ll)2e18 + 1386; const ld eps = 0.000000000000001; const int MOD = 1e9 + 7; inline int mod_add(int a, int b){ int res = a + b; return (res >= MOD? res - MOD : res); } inline int mod_neg(int a, int b){ int res = (abs(a - b) < MOD? a - b : (a - b) % MOD); return (res < 0? res + MOD : res); } inline int mod_mlt(int a, int b){ return (1ll * a * b % MOD); } inline string intToString(ll a){ char x[100]; sprintf(x, "%lld", a); string s = x; return s; } inline ll stringToInt(string s){ ll res; char x[100]; strcpy(x, s.c_str()); sscanf(x, "%lld", &res); return res; } inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); } const int MAXN = 2e5 + 5, LOG = 23; int n, m, q, par[MAXN][LOG], h[MAXN], psU[MAXN], psD[MAXN], st[MAXN], mnback[MAXN], timer, ans[MAXN], jahat[MAXN]; bool boreshi[MAXN], mark[MAXN], mark2[MAXN]; vector<PII> N[MAXN]; void dfs(int v, int lst, int height){ mark[v] = 1; h[v] = height++; mnback[v] = st[v] = timer++; for (auto [u, e] : N[v]){ if (!mark[u]){ par[u][0] = v; for (int i = 1; i < LOG; i++){ par[u][i] = par[par[u][i - 1]][i - 1]; } dfs(u, e, height); if (mnback[u] > st[v]) boreshi[e] = 1; mnback[v] = min(mnback[v], mnback[u]); } else if (e != lst){ mnback[v] = min(mnback[v], st[u]); } } } int balaaaaaa(int v, int k){ for (int i = LOG - 1; i >= 0; i--){ if (k >> i & 1){ v = par[v][i]; } } return v; } int LCA(int u, int v){ if (h[u] > h[v]) swap(u, v); v = balaaaaaa(v, h[v] - h[u]); if (u == v) return v; for (int i = LOG - 1; i >= 0; i--){ if (par[v][i] != par[u][i]){ v = par[v][i], u = par[u][i]; } } return par[u][0]; } void dfs_ans(int v){ mark2[v] = 1; for (auto [u, e] : N[v]){ if (!mark2[u]){ dfs_ans(u); psD[v] += psD[u], psU[v] += psU[u]; if (boreshi[e] && (psD[u] || psU[u])){ if ((jahat[e] == v && psD[u]) || (jahat[e] == u && psU[u])) ans[e] = 1; else ans[e] = 2; } else ans[e] = 3; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++){ int x, y; cin >> x >> y; N[x].PB({y, i}), N[y].PB({x, i}); jahat[i] = x; } for (int i = 1; i <= n; i++){ if (!mark2[i]){ dfs_ans(i); for (int j = 0; j < LOG; j++){ par[i][j] = i; } dfs(i, -1, 1); } } cin >> q; while (q--){ int u, v; cin >> u >> v; int lca = LCA(u, v); psU[u]++, psU[lca]--; psD[v]++, psD[lca]--; } fill(mark2, mark2 + MAXN, 0); for (int i = 1; i <= n; i++){ if (!mark2[i]){ dfs_ans(i); } } for (int i = 1; i <= m; i++){ if (ans[i] == 1) cout << 'R'; else if (ans[i] == 2) 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...