Submission #490951

#TimeUsernameProblemLanguageResultExecution timeMemory
490951hohohahaOne-Way Streets (CEOI17_oneway)C++14
0 / 100
1 ms460 KiB
// #pragma GCC optimize("Ofast") // #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") // #pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/trie_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; // using namespace __gnu_cxx; #define li long long #define ld long double #define ii pair<int, int> #define vi vector<int> #define vvi vector<vi> #define fi first #define se second #define mp make_pair #define pb push_back #define pf push_front #define eb emplace_back #define em emplace #define ob pop_back #define om pop #define of pop_front #define fr front #define bc back #define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i) #define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i) #define all(x) begin(x), end(x) #define sz(x) ((int)(x).size()) #define bitc __builtin_popcountll mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rand rng #define endl '\n' #define sp ' ' #define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); void solve(); signed main() { // freopen("input.inp","r",stdin); // freopen("output.out","w",stdout); fastio(); int tc = 1; fori(test, 1, tc) { solve(); } return 0; } #define int long long const ld pi = 4 * atan(1.0), eps = 1e-9; const int maxn = 2005; int n, m, q; int low[maxn], in[maxn], inptr; bool isbr[maxn]; vector<ii> g[maxn]; set<ii> S[maxn]; ii last[maxn]; void dfs(int i, int pe, int p) { low[i] = in[i] = ++inptr; for(ii t: g[i]) { int j= t.fi, id = t.se; if(!in[j]) { dfs(j, id, i); low[i] = min(low[i], low[j]); if(S[i].size() < S[j].size()) S[i].swap(S[j]); for(ii t: S[j]) { if(S[i].count({t.fi, t.se ^ 1})) { S[i].erase({t.fi, t.se ^ 1}); } else { S[i].insert(t); } } } else if(id - pe and low[j] < low[i]) { low[i] = min(low[i], in[j]); } } if(low[i] >= in[i]) { if(S[i].size() and S[i].begin() -> se == 0) last[pe] = {i, p}; else if(S[i].size() and S[i].begin() ->se == 1) last[pe] = {p, i}; } } void solve() { cin >> n >> m; fori(i, 1, m) { int u, v; cin >> u >> v; g[u].eb(v, i); g[v].eb(u, i); } cin >> q; fori(i,1, q){ int u,v; cin >> u >> v; S[u].em(i, 0); S[v].em(i, 1); } dfs(1, -1, 1); fori(i,1, m) { if(!last[i].fi) cout << "B"; else if(last[i].fi <last[i].se) cout << "L"; else cout << "R"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...