제출 #711245

#제출 시각아이디문제언어결과실행 시간메모리
711245WonderfulWhaleOne-Way Streets (CEOI17_oneway)C++17
100 / 100
153 ms44328 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back #define pii pair<int, int> #define st first #define nd second #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() const int MAXN = 100009; const int LOG = 17; int n, m; int jump[MAXN]; bool bridge[MAXN]; int dep[MAXN]; vector<pii> G[MAXN]; vector<pii> G2[MAXN]; int S[MAXN]; int E[MAXN]; pii edge[MAXN]; int ans[MAXN]; bool vis[MAXN]; int tab[MAXN]; int cnt; int T, tin[MAXN], tout[MAXN], jp2[MAXN][LOG]; void dfs1(int x, int d, int pre) { vis[x] = true; dep[x] = d; jump[x] = d; for(auto [z, id]:G[x]) { if(id==pre) continue; if(!vis[z]) { dfs1(z, d+1, id); jump[x] = min(jump[x], jump[z]); } else { jump[x] = min(jump[x], dep[z]); } } if(pre==-1) return; if(jump[x] == d) bridge[pre] = true; //cout << "teraz: " << x << " skok: " << jump[x] << "\n"; //cout << pre << " " << bridge[pre] << "\n"; } void dfs2(int x, int col) { vis[x] = true; tab[x] = col; for(auto [z, id]:G[x]) { if(!bridge[id]) { if(!vis[z]) dfs2(z, col); } else { if(vis[z]) { G2[col].pb({tab[z], id}); } else { dfs2(z, ++cnt); G2[col].pb({tab[z], id}); } } } } void dfs3(int x, int y) { //cout << "licze: " << x << " " << y << "\n"; vis[x] = true; tin[x] = ++T; jp2[x][0] = y; for(int i=1;i<LOG;i++) { jp2[x][i] = jp2[jp2[x][i-1]][i-1]; } for(auto [z, id]:G2[x]) { if(z!=y) dfs3(z, x); } tout[x] = ++T; } bool is_ancestor(int x, int y) { return tin[x]<=tin[y]&&tout[x]>=tout[y]; } int lca(int x, int y) { if(is_ancestor(x, y)) return x; if(is_ancestor(y, x)) return y; for(int i=LOG-1;i>=0;i--) { if(!is_ancestor(jp2[x][i], y)) { x = jp2[x][i]; } } return jp2[x][0]; } pii dfs4(int x, int pre) { vis[x] = true; pii val = {0, 0}; for(auto [z, id]:G2[x]) { if(id==pre) continue; pii nval = dfs4(z, id); val.st += nval.st; val.nd += nval.nd; } val.st += S[x]; val.nd += E[x]; //cout << "v: " << x << " " << val.st << " " << val.nd << "\n"; assert(!val.st||!val.nd); if(pre==-1) return val; if(val.st) { //cout << "tu: " << x << " "<< tab[edge[pre].st] << "\n"; if(x == tab[edge[pre].st]) { //cout << "set: " << pre << " 1\n"; ans[pre] = -1; } else { //cout << "set: " << pre << " 2\n"; ans[pre] = 1; } } else if(val.nd) { //cout << "tu\n"; if(x == tab[edge[pre].st]) { //cout << "set: " << pre << " 3\n"; ans[pre] = 1; } else { //cout << "set: " << pre << " 4\n"; ans[pre] = -1; } } return val; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i=0;i<m;i++) { int a, b; cin >> a >> b; G[a].pb({b, i}); G[b].pb({a, i}); edge[i] = {a, b}; } for(int i=1;i<=n;i++) { if(!vis[i]) { dfs1(i, 0, -1); } } memset(vis, 0, sizeof(vis)); for(int i=1;i<=n;i++) { if(!vis[i]) { dfs2(i, ++cnt); } } for(int i=1;i<=n;i++) { //cout << i << ": " << tab[i] << "\n"; } //cout << "graf\n"; for(int i=1;i<=cnt;i++) { //cout << i << ":\n"; for(pii x:G2[i]) { //cout << x.st << " " << x.nd << "\n"; } } //cout << "koniec\n"; memset(vis, 0, sizeof(vis)); for(int i=1;i<=cnt;i++) { if(!vis[i]) { dfs3(i, 0); } } tin[0] = 0; tout[0] = ++T; int q; cin >> q; while(q--) { int a, b; cin >> a >> b; S[tab[a]]++; E[tab[b]]++; int Lca = lca(tab[a], tab[b]); //cout << tab[a] << " " << tab[b] << " " << Lca << " lca\n"; S[Lca]--; E[Lca]--; } for(int i=1;i<=cnt;i++) { //cout << i << ": "<< S[i] << " " << E[i] << "\n"; } memset(vis, 0, sizeof(vis)); for(int i=1;i<=cnt;i++) { if(!vis[i]) { dfs4(i, -1); } } for(int i=0;i<m;i++) { if(ans[i]==0) { cout << "B"; } else if(ans[i]==1) { cout << "L"; } else { cout << "R"; } } cout << "\n"; }

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

oneway.cpp: In function 'int32_t main()':
oneway.cpp:160:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  160 |   for(pii x:G2[i]) {
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...