Submission #114457

#TimeUsernameProblemLanguageResultExecution timeMemory
114457PeppaPigOne-Way Streets (CEOI17_oneway)C++14
0 / 100
4 ms2688 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 1e5+5; int n, m, p; map<pii, int> M; vector<vector<int> > g(N), cc; vector<pii> E; int pre[N], low[N]; bitset<N> br; void tarjan(int u, int p) { static int idx = 0; static stack<int> S; pre[u] = low[u] = ++idx; S.emplace(u); for(int v : g[u]) if(v != p) { if(!pre[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if(low[v] > pre[u]) { if(M.count(pii(u, v))) br[M[pii(u, v)]] = true; else br[M[pii(v, u)]] = true; cc.emplace_back(vector<int>()); while(cc.back().empty() || cc.back().back() != v) { cc.back().emplace_back(S.top()); S.pop(); } } } else low[u] = min(low[u], pre[v]); } if(u == p) { cc.emplace_back(vector<int>()); while(!S.empty()) { cc.back().emplace_back(S.top()); S.pop(); } } } int id[N]; void gen_bbt() { g.clear(), M.clear(); g.emplace_back(vector<int>()); for(vector<int>& c : cc) { g.emplace_back(vector<int>()); for(int v : c) id[v] = g.size() - 1; } for(int i = 1, a, b; i <= m; i++) if(br[i]) { tie(a, b) = E[i-1]; M[pii(id[a], id[b])] = i; M[pii(id[b], id[a])] = i; g[id[a]].emplace_back(id[b]); g[id[b]].emplace_back(id[a]); } } int par[N][18], dep[N]; void dfs(int u, int p) { dep[u] = dep[p] + 1, par[u][0] = p; for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1]; for(int v : g[u]) if(v != p) dfs(v, u); } int lca(int a, int b) { if(dep[a] < dep[b]) swap(a, b); for(int i = 17; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i]; if(a == b) return a; for(int i = 17; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i]; return par[a][0]; } int orient[N]; int main() { scanf("%d %d", &n, &m); for(int i = 1, a, b; i <= m; i++) { scanf("%d %d", &a, &b); M[pii(a, b)] = i; E.emplace_back(a, b); g[a].emplace_back(b), g[b].emplace_back(a); } for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, i); gen_bbt(); for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, 0); scanf("%d", &p); for(int i = 1, a, b; i <= p; i++) { scanf("%d %d", &a, &b); a = id[a], b = id[b]; int l = lca(a, b); while(a != l) { int eid = M[pii(a, par[a][0])]; if(orient[eid] != 0) break; if(E[eid-1] == pii(a, par[a][0])) orient[eid] = 1; else orient[eid] = -1; a = par[a][0]; } while(b != l) { int eid = M[pii(b, par[b][0])]; if(orient[eid] != 0) break; if(E[eid-1] == pii(b, par[b][0])) orient[eid] = -1; else orient[eid] = 1; b = par[b][0]; } } for(int i = 1; i <= m; i++) { if(orient[i] == 0) printf("B"); else if(orient[i] == -1) printf("R"); else printf("L"); } printf("\n"); return 0; }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, 0);
                    ~~^~~~~~~~~~
oneway.cpp:87: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:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...