제출 #148090

#제출 시각아이디문제언어결과실행 시간메모리
148090WhipppedCreamOne-Way Streets (CEOI17_oneway)C++17
100 / 100
254 ms30668 KiB
//Power Of Ninja Go #include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vii vector< ii > #define pb push_back const int maxn = 1e5+5; vii adj[maxn]; vii tree[maxn]; ii e[maxn]; bool isB[maxn]; int num[maxn]; int low[maxn]; int bcc[maxn]; int dp[22][maxn]; int ans[maxn]; int link[maxn]; int sw[maxn]; int dep[maxn]; int chil[maxn]; int cnt; queue<int> Q; void dfs(int u, int id) { num[u] = low[u] = ++cnt; for(auto edge : adj[u]) { int v = edge.X, f = edge.Y; if(!num[v]) { dfs(v, f); low[u] = min(low[u], low[v]); if(low[v]> num[u]) { isB[f] = true; } } else if(f != id) low[u] = min(low[u], num[v]); } } void play(int u) { bcc[u] = cnt; for(auto edge : adj[u]) { int v = edge.X, id = edge.Y; if(!isB[id] && !bcc[v]) play(v); } } void dfsT(int u, int p) { int has = 0; for(auto edge : tree[u]) { int v = edge.X, id = edge.Y; if(v == p) continue; dp[0][v] = u; dep[v] = 1+dep[u]; link[v] = id; has = 1; dfsT(v, u); chil[u]++; } if(!has) Q.push(u); } int LCA(int u, int v) { if(dep[u]< dep[v]) swap(u, v); for(int i = 20; i>= 0; i--) { int k = dp[i][u]; if(dep[k]>= dep[v]) u = k; } if(u == v) return u; for(int i = 20; i>= 0; i--) { int a = dp[i][u], b = dp[i][v]; if(a == b) continue; u = a; v = b; } return dp[0][u]; } int main() { //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif int n, m; cin >> n >> m; for(int i = 1; i<= m; i++) { scanf("%d %d", &e[i].X, &e[i].Y); if(e[i].X == e[i].Y) continue; adj[e[i].X].pb(ii(e[i].Y, i)); adj[e[i].Y].pb(ii(e[i].X, i)); } for(int i = 1; i<= n; i++) if(!num[i]) dfs(i, 0); //for(int i = 1; i<= m; i++) printf("%d ", isB[i]); printf("\n"); memset(num, 0, sizeof num); cnt = 0; for(int i = 1; i<= n; i++) if(!bcc[i]){ cnt++; play(i); } //for(int i = 1; i<= n; i++) printf("%d ", bcc[i]); printf("\n"); for(int i = 1; i<= m; i++) { if(isB[i]) { int u = e[i].X, v = e[i].Y; //printf("(%d, %d) is (%d, %d)\n", u, v, bcc[u], bcc[v]); tree[bcc[u]].pb(ii(bcc[v], i)); tree[bcc[v]].pb(ii(bcc[u], i)); } } for(int i = 1; i<= cnt; i++) if(!dep[i]) { dep[i]++; dfsT(i, 0); } for(int i = 1; i<= 20; i++) { for(int j = 1; j<= cnt; j++) dp[i][j] = dp[i-1][dp[i-1][j]]; } int p; cin >> p; while(p--) { int a, b; cin >> a >> b; a = bcc[a], b = bcc[b]; if(a == b) continue; sw[a]++; sw[b]--; } while(!Q.empty()) { int u = Q.front(); Q.pop(); int p = dp[0][u]; sw[p] += sw[u]; chil[p]--; if(p && chil[p] == 0) Q.push(p); if(sw[u]> 0) { int id = link[u]; if(bcc[e[id].X] == u) ans[id] = 1; else ans[id] = -1; } else if(sw[u]< 0) { int id = link[u]; if(bcc[e[id].X] == u) ans[id] = -1; else ans[id] = 1; } } for(int i = 1; i<= m; i++) { if(ans[i] == 1) printf("R"); else if(ans[i] == -1) printf("L"); else printf("B"); } printf("\n"); }

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &e[i].X, &e[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...