Submission #65704

#TimeUsernameProblemLanguageResultExecution timeMemory
65704polyfishOne-Way Streets (CEOI17_oneway)C++14
0 / 100
7 ms5112 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int MAX_N = 100002; const int LG_N = 19; const int INF = 1e9; struct edge { int u, v; }; int n, m, nTime, num[MAX_N], low[MAX_N], l[MAX_N], p[LG_N+2][MAX_N]; int nCC, cc_id[MAX_N], up_query[MAX_N], down_query[MAX_N]; bool bridge[MAX_N], visited[MAX_N]; edge e[MAX_N]; vector<pair<int, int> > g[MAX_N], tr[MAX_N]; char res[MAX_N]; void enter() { cin >> n >> m; for (int i=1; i<=m; ++i) { cin >> e[i].u >> e[i].v; g[e[i].u].push_back(make_pair(e[i].v, i)); g[e[i].v].push_back(make_pair(e[i].u, i)); } } void dfs(int u, int par) { num[u] = low[u] = ++nTime; bool ok = false; for (int i=0; i<g[u].size(); ++i) { int v = g[u][i].first, id = g[u][i].second; if (v==par && !ok) ok = true; else { if (num[v]) low[u] = min(low[u], num[v]); else { dfs(v, u); low[u] = min(low[u], low[v]); } if (num[u]<low[v]) bridge[id] = true; else res[id] = 'B'; } } } void find_connected_component(int u) { cc_id[u] = nCC; for (int i=0; i<g[u].size(); ++i) { int v = g[u][i].first, id = g[u][i].second; if (cc_id[v]==0 && !bridge[id]) find_connected_component(v); } } void fix_root(int u) { for (int i=0; i<tr[u].size(); ++i) { int v = tr[u][i].first; if (v!=p[0][u]) { p[0][v] = u; l[v] = l[u] + 1; fix_root(v); } } } void init_tree() { for (int i=1; i<=n; ++i) if (num[i]==0) dfs(1, 0); for (int i=1; i<=n; ++i) { if (cc_id[i]==0) { ++nCC; find_connected_component(i); } } //PR(bridge, m); for (int i=1; i<=m; ++i) { if (bridge[i]) { int u = cc_id[e[i].u], v = cc_id[e[i].v]; tr[u].push_back(make_pair(v, i)); tr[v].push_back(make_pair(u, i)); } } n = nCC; for (int i=1; i<=n; ++i) { if (l[i]==0) { l[i] = 1; fix_root(i); } } for (int i=1; i<=LG_N; ++i) for (int j=1; j<=n; ++j) p[i][j] = p[i-1][p[i-1][j]]; } int lca(int x, int y) { for (int k=LG_N; k>=0; --k) if (l[p[k][x]]>=l[y]) x = p[k][x]; for (int k=LG_N; k>=0; --k) if (l[p[k][y]]>=l[x]) y = p[k][y]; for (int k=LG_N; k>=0; --k) { if (p[k][x]!=p[k][y]) { x = p[k][x]; y = p[k][y]; } } while (x != y) { x = p[0][x]; y = p[0][y]; } return x; } void init_query() { int nQuery; cin >> nQuery; while (nQuery--) { int u, v; cin >> u >> v; u = cc_id[u], v = cc_id[v]; if (u!=v) { //cerr << u << ' ' << v << '\n'; int anc = lca(u, v); ++up_query[u]; --up_query[anc]; ++down_query[v]; --down_query[anc]; } } } void solve(int u) { visited[u] = true; for (int i=0; i<tr[u].size(); ++i) { int v = tr[u][i].first, id = tr[u][i].second; if (v!=p[0][u]) { solve(v); up_query[u] += up_query[v]; down_query[u] += down_query[v]; if (up_query[v]>0) res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(v, u) ? 'R' : 'L'); else if (down_query[v]>0) res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(u, v) ? 'R' : 'L'); else res[id] = 'B'; } } } int main() { //#define OFFLINE_JUDGE doraemon #ifdef OFFLINE_JUDGE freopen(FILE_NAME".inp", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); init_tree(); init_query(); for (int i=1; i<=n; ++i) if (!visited[i]) solve(i); for (int i=1; i<=m; ++i) cout << res[i]; }

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
oneway.cpp: In function 'void find_connected_component(int)':
oneway.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
oneway.cpp: In function 'void fix_root(int)':
oneway.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<tr[u].size(); ++i) {
                ~^~~~~~~~~~~~~
oneway.cpp: In function 'void solve(int)':
oneway.cpp:148:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<tr[u].size(); ++i) {
                ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...