Submission #627092

#TimeUsernameProblemLanguageResultExecution timeMemory
627092Do_you_copyOne-Way Streets (CEOI17_oneway)C++17
0 / 100
4 ms5076 KiB
#include <bits/stdc++.h> //#define int long long #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 1e5 + 1; int n, m, k; struct TDSU{ vector <pii> save; vector <int> lab; TDSU(){} TDSU(int _n){ lab.resize(_n, -1); } inline void resize(int _n){ lab.resize(_n, -1); } inline int find_set(int u){ if (lab[u] < 0) return u; return lab[u] = find_set(lab[u]); } inline int find(int u){ if (lab[u] < 0) return u; return find(lab[u]); } inline void merge(int u, int v){ if (lab[u] > lab[v]) swap(u, v); save.pb({v, lab[v]}); lab[u] += lab[v]; lab[v] = u; } inline void undo(){ int v = save.back().fi; int u = lab[v]; lab[v] = save.back().se; lab[u] -= lab[v]; save.pop_back(); } inline void clear(){ lab.clear(); save.clear(); } inline void reset(int _n){ clear(); resize(_n); } inline void roll_back(int _n){ while (save.size() > _n) undo(); } }; TDSU dsu; int timedfs, low[maxN], num[maxN]; int id[maxN]; int mark[maxN]; int node_cnt; struct TEdge{ int u, v, idx; }; TEdge e[maxN]; vector <TEdge> adj[maxN]; void dfs(int u, int p){ low[u] = num[u] = ++timedfs; for (auto i: adj[u]){ int v = i.u ^ i.v ^ u; if (v == p) continue; if (!num[v]){ dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] == num[v]) mark[i.idx] = 1; } else{ low[u] = min(low[u], num[v]); } } } vector <pii> adj1[maxN]; int lift[20][maxN]; int depth[maxN]; int val[maxN]; void dfs1(int u, int p){ lift[u][0] = p; depth[u] = depth[p] + 1; for (int i = 1; i < 20; ++i){ lift[u][i] = lift[lift[u][i - 1]][i - 1]; if (!lift[u][i]) break; } for (auto i: adj1[u]){ int v = i.fi; if (v == p) continue; dfs1(v, u); } } int lca(int u, int v){ if (depth[u] < depth[v]) swap(u, v); int k = depth[u] - depth[v]; while (k){ int t = k & -k; u = lift[u][__lg(t)]; k -= t; } if (u == v) return u; for (int i = 19; i >= 0; --i){ if (lift[u][i] != lift[v][i]){ u = lift[u][i]; v = lift[v][i]; } } return lift[u][0]; } void dfs2(int u, int p){ for (auto i: adj1[u]){ int v = i.fi; if (v == p) continue; dfs2(v, u); val[u] += val[v]; if (!val[v]){ mark[abs(i.se)] = 0; } else if (val[v] * i.se < 0) mark[abs(i.se)] = 1; else mark[abs(i.se)] = -1; } } void Init(){ cin >> n >> m; for (int i = 1; i <= m; ++i){ cin >> e[i].u >> e[i].v; e[i].idx = i; adj[e[i].u].pb(e[i]); adj[e[i].v].pb(e[i]); } for (int i = 1; i <= n; ++i){ if (!num[i]) dfs(i, 0); } dsu.resize(n + 1); vector <int> bridge; for (int i = 1; i <= m; ++i){ if (!mark[i]){ int x = dsu.find_set(e[i].u); int y = dsu.find_set(e[i].v); if (x != y){ dsu.merge(x, y); } } else bridge.pb(i); } for (int i = 1; i <= n; ++i){ int j = dsu.find_set(i); if (!id[j]) id[j] = ++node_cnt; id[i] = id[j]; } for (int i: bridge){ int u = id[e[i].u]; int v = id[e[i].v]; adj1[u].pb({v, i}); adj1[v].pb({u, -i}); } for (int i = 1; i <= node_cnt; ++i){ if (!lift[i][0]){ dfs1(i, 0); } } cin >> k; for (int i = 1; i <= k; ++i){ int u, v; cin >> u >> v; u = id[u]; v = id[v]; ++val[u]; --val[v]; } for (int i = 1; i <= node_cnt; ++i){ if (!lift[i][0]){ dfs2(i, 0); } } for (int i = 1; i <= m; ++i){ if (!mark[i]) cout << 'B'; else if (mark[i] < 0) cout << 'L'; else cout << 'R'; } } #define debu #define taskname "test" signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); #ifdef debug freopen(taskname".out", "w", stdout); #endif } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << 1000 * double(clock()) / CLOCKS_PER_SEC; #ifndef debug cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n"; #endif } }

Compilation message (stderr)

oneway.cpp: In member function 'void TDSU::roll_back(int)':
oneway.cpp:72:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         while (save.size() > _n) undo();
      |                ~~~~~~~~~~~~^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:218:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...