Submission #92956

#TimeUsernameProblemLanguageResultExecution timeMemory
92956KastandaOne-Way Streets (CEOI17_oneway)C++11
100 / 100
241 ms29816 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; const int N = 100005, LG = 18; int n, m, q, from[N], to[N], M[N], H[N], Mn[N]; int cp, Hc[N], C[N], P[N][LG], up[N], dn[N]; int qa[N], qb[N]; char R[N]; vector < int > Adj[N], Ad[N]; void DFS(int v, int p) { Mn[v] = H[v]; M[v] = 1; for (int &id : Adj[v]) { if (id == p) continue; int u = from[id] ^ to[id] ^ v; if (M[u] == 2) continue; else if (M[u] == 1) Mn[v] = min(Mn[v], H[u]); else { H[u] = H[v] + 1; DFS(u, id); Mn[v] = min(Mn[v], Mn[u]); } } M[v] = 2; } void DFS2(int v, int p, int pc) { C[v] = pc; M[v] = 1; for (int &id : Adj[v]) { if (id == p) continue; int u = from[id] ^ to[id] ^ v; if (M[u]) continue; if (Mn[u] < H[u]) DFS2(u, id, pc); else { ++ cp; Ad[pc].pb(id); Ad[cp].pb(id); P[cp][0] = pc; Hc[cp] = Hc[pc] + 1; DFS2(u, id, cp); } } } void DFS3(int v, int p) { M[v] = 1; for (int &id : Ad[v]) { if (id == p) continue; int u = from[id]; if (C[u] == v) u = to[id]; DFS3(C[u], id); up[v] = max(up[v], up[C[u]] - 1); dn[v] = max(dn[v], dn[C[u]] - 1); } if (up[v] && dn[v]) exit(1); if (up[v]) { if (C[from[p]] == v) R[p] = 'R'; else R[p] = 'L'; } if (dn[v]) { if (C[from[p]] == v) R[p] = 'L'; else R[p] = 'R'; } } inline int LCA(int v, int u) { if (Hc[v] < Hc[u]) swap(v, u); for (int i = 0; i < LG; i++) if ((Hc[v] - Hc[u]) & (1 << i)) v = P[v][i]; if (v == u) return (v); for (int i = LG - 1; ~i; i--) if (P[v][i] != P[u][i]) v = P[v][i], u = P[u][i]; return (P[v][0]); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &from[i], &to[i]); Adj[from[i]].pb(i); Adj[to[i]].pb(i); R[i] = 'B'; } scanf("%d", &q); for (int i = 1; i <= q; i++) scanf("%d%d", &qa[i], &qb[i]); for (int i = 1; i <= n; i++) if (!M[i]) DFS(i, -1); memset(M, 0, sizeof(M)); for (int i = 1; i <= n; i++) if (!M[i]) cp ++, DFS2(i, -1, cp); for (int i = 1; i < LG; i++) for (int v = 1; v <= cp; v ++) P[v][i] = P[P[v][i - 1]][i - 1]; for (int i = 1; i <= q; i++) { int a = qa[i], b = qb[i]; if (C[a] == C[b]) continue; int lca = LCA(C[a], C[b]); up[C[a]] = max(up[C[a]], Hc[C[a]] - Hc[lca]); dn[C[b]] = max(dn[C[b]], Hc[C[b]] - Hc[lca]); } memset(M, 0, sizeof(M)); for (int i = 1; i <= cp; i++) if (!M[i]) DFS3(i, -1); printf("%s\n", R + 1); return (0); }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:101: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:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &from[i], &to[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
oneway.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &qa[i], &qb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...