Submission #131550

#TimeUsernameProblemLanguageResultExecution timeMemory
131550SamAndOne-Way Streets (CEOI17_oneway)C++17
100 / 100
456 ms46840 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair const int N = 100005, l = 20; int n, m; pair<int, int> r[N]; vector<int> a[N]; vector<int> b[N]; bool bri[N]; int c[N]; int tin[N], ti, fup[N]; void dfs0(int x, int p) { c[x] = 1; fup[x] = tin[x] = ti++; for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p) continue; if (c[h]) fup[x] = min(fup[x], tin[h]); else { dfs0(h, x); if (fup[h] > tin[x]) bri[b[x][i]] = true; fup[x] = min(fup[x], fup[h]); } } } int k; void dfs1(int x) { c[x] = k; for (int i = 0; i < a[x].size(); ++i) { if (bri[b[x][i]]) continue; int h = a[x][i]; if (!c[h]) dfs1(h); } } vector<int> g[N]; vector<int> gg[N]; bool c1[N]; int tout[N]; int pp[N][l]; bool dfs(int x, int p) { c1[x] = true; tin[x] = ti++; pp[x][0] = p; for (int i = 1; i < l; ++i) { pp[x][i] = pp[pp[x][i - 1]][i - 1]; } for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) continue; dfs(h, x); } tout[x] = ti++; } bool par(int x, int y) { return (tin[x] <= tin[y] && tout[x] >= tout[y]); } int lca(int x, int y) { if (par(x, y)) return x; if (par(y, x)) return y; for (int i = l - 1; i >= 0; --i) { if (!par(pp[x][i], y)) x = pp[x][i]; } return pp[x][0]; } char ans[N]; int qu[N], qd[N]; void dfsf(int x, int p, int j) { for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) continue; dfsf(h, x, gg[x][i]); qu[x] += qu[h]; qd[x] += qd[h]; } if (qu[x]) { if (m_p(x, p) == m_p(c[r[j].first], c[r[j].second])) ans[j - 1] = 'R'; else ans[j - 1] = 'L'; } if (qd[x]) { if (m_p(p, x) == m_p(c[r[j].first], c[r[j].second])) ans[j - 1] = 'R'; else ans[j - 1] = 'L'; } } int main() { //freopen("input.txt", "r", stdin); map<pair<int, int> , int> mp; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { int x, y; scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); b[x].push_back(i); b[y].push_back(i); r[i] = m_p(x, y); if (x > y) swap(x, y); mp[m_p(x, y)]++; } for (int i = 1; i <= n; ++i) { if (!c[i]) dfs0(i, -1); } for (int i = 1; i <= m; ++i) { if (bri[i]) { if (mp[m_p(min(r[i].first, r[i].second), max(r[i].first, r[i].second))] > 1) bri[i] = false; } } memset(c, 0, sizeof c); for (int x = 1; x <= n; ++x) { if (!c[x]) { ++k; dfs1(x); } } for (int x = 1; x <= n; ++x) { for (int i = 0; i < a[x].size(); ++i) { if (bri[b[x][i]]) { g[c[x]].push_back(c[a[x][i]]); gg[c[x]].push_back(b[x][i]); } } } for (int i = 1; i <= m; ++i) ans[i - 1] = 'B'; vector<int> v; for (int i = 1; i <= k; ++i) { if (!c1[i]) { v.push_back(i); dfs(i, i); } } int q; scanf("%d", &q); while (q--) { int x, y; scanf("%d%d", &x, &y); x = c[x]; y = c[y]; int t = lca(x, y); qu[x]++; qu[t]--; qd[y]++; qd[t]--; } for (int i = 0; i < v.size(); ++i) { dfsf(v[i], v[i], -1); } cout << ans << endl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void dfs0(int, int)':
oneway.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'bool dfs(int, int)':
oneway.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
oneway.cpp: In function 'void dfsf(int, int, int)':
oneway.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:164:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
oneway.cpp:201:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
oneway.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
oneway.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...