Submission #104951

#TimeUsernameProblemLanguageResultExecution timeMemory
104951eriksuenderhaufOne-Way Streets (CEOI17_oneway)C++11
100 / 100
375 ms72680 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; int U[MAXN], V[MAXN], ans[MAXN], br[MAXN], id[MAXN]; bool vis[MAXN], mrk[MAXN]; int low[MAXN], disc[MAXN]; int npar[20][MAXN], depth[MAXN], f[MAXN]; int qry[MAXN][3]; vii adj[MAXN], tree[MAXN]; int t = 0; void dfs(int u, int p) { low[u] = disc[u] = t++; vis[u] = 1; for (pii nx: adj[u]) { int v = nx.fi; if (nx.se == p) continue; if (!vis[v]) { dfs(v, nx.se); low[u] = min(low[u], low[v]); if (low[v] > disc[u]) br[nx.se] = 1; } else low[u] = min(low[u], disc[v]); } } int cur = 0; void tr(int u) { deque<int> pq; pq.pb(u); vis[u] = 1; int cmp = cur; id[u] = cmp; while (!pq.empty()) { int ur = pq.front(); pq.pop_front(); for (pii nx: adj[ur]) { int v = nx.fi; if (vis[v]) continue; if (br[nx.se]) { cur++; tree[cur].pb({cmp, nx.se}); tree[cmp].pb({cur, nx.se}); tr(v); } else { pq.pb(v); id[v] = cmp; vis[v] = 1; } } } } void dfs2(int u, int p, int d) { depth[u] = d; for (pii nx: tree[u]) { int v = nx.fi; if (v != p) { f[v] = nx.se; dfs2(v, u, d + 1); npar[0][v] = u; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); int d = depth[v] - depth[u]; for (int i = 16; i >= 0; i--) if ((d >> i) & 1) v = npar[i][v]; if (u == v) return v; for (int i = 16; i >= 0; i--) if (npar[i][u] != npar[i][v]) u = npar[i][u], v = npar[i][v]; return npar[0][u]; } int main() { int n, m, p; ni(n), ni(m); for (int i = 0; i < m; i++) { ni(U[i]), ni(V[i]); U[i]--, V[i]--; adj[U[i]].pb({V[i], i}); adj[V[i]].pb({U[i], i}); } int c = 0; vi tmp, tmp2; for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, -1), c++, tmp.pb(i); memset(vis, 0, sizeof vis); for (int i = 0; i < c; i++) tmp2.pb(cur), tr(tmp[i]), cur++; for (int i= 0; i < c; i++) dfs2(tmp2[i], -1, 0); for (int i = 1; i < 17; i++) for (int j = 0; j < cur; j++) npar[i][j] = npar[i - 1][npar[i - 1][j]]; vii arr; ni(p); for (int i = 0; i < p; i++) { int u, v; ni(u), ni(v); u--, v--; u = id[u], v = id[v]; if (u == v) continue; int l = lca(u, v); arr.pb({depth[l], i}); qry[i][0] = u, qry[i][1] = v, qry[i][2] = l; } sort(arr.begin(), arr.end()); for (pii nx: arr) { int u = qry[nx.se][0], v = qry[nx.se][1], l = qry[nx.se][2]; int x = u; while (x != l) { if (mrk[f[x]]) break; mrk[f[x]] = 1; if (id[U[f[x]]] == x) ans[f[x]] = 2; else ans[f[x]] = 1; x = npar[0][x]; } x = v; while (x != l) { if (mrk[f[x]]) break; mrk[f[x]] = 1; if (id[U[f[x]]] == x) ans[f[x]] = 1; else ans[f[x]] = 2; x = npar[0][x]; } } for (int i = 0; i < m; i++) if (ans[i] == 0) printf("B"); else if (ans[i] == 1) printf("L"); else printf("R"); enl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(m);
          ^
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(U[i]), ni(V[i]);
                 ^
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
oneway.cpp:145:5: note: in expansion of macro 'ni'
     ni(p);
     ^~
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(u), ni(v);
              ^
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...