Submission #558444

#TimeUsernameProblemLanguageResultExecution timeMemory
558444uroskOne-Way Streets (CEOI17_oneway)C++14
0 / 100
3 ms5076 KiB
// __builtin_popcount(x) // __builtin_popcountll(x) #define here cerr<<"===========================================\n" #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) int(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} using namespace std; #define maxn 100005 ll n,m; vector<ll> g[maxn]; ll in[maxn]; vector<pll> edge; ll it = 1; ll low[maxn]; bool vis[maxn]; stack<ll> stk; ll dsu[maxn]; ll comp = 1; void dfs(ll u,ll par){ low[u] = in[u] = it++; vis[u] = 1; stk.push(u); for(ll s : g[u]){ if(s==par) continue; if(vis[s]){ low[u] = min(low[u],low[s]); }else{ dfs(s,u); if(low[s]>in[u]){ while(sz(stk)){ ll v = stk.top(); stk.pop(); dsu[v] = comp; if(v==s) break; } comp++; } low[u] = min(low[u],low[s]); } } } map<pll,ll> cnt; map<pll,bool> ans; ll con[maxn]; ll root(ll x){ while(x!=con[x]){ con[x] = con[con[x]]; x = con[x]; } return x; } void upd(ll x,ll y){ x = root(x); y = root(y); con[x] = con[y]; } ll q; #define lg 25 ll in2[maxn]; ll out2[maxn]; vector<ll> v[maxn]; ll st[maxn][lg]; void dfs2(ll u,ll par){ vis[u] =1; st[u][0] = par; in2[u] = it++; for(ll s : v[u]){ if(s==par) continue; dfs2(s,u); } out2[u] = it-1; } bool intree(ll x,ll y){ return in2[x]>=in2[y]&&out2[y]>=out2[x]; } ll lca(ll x,ll y){ if(intree(x,y)) return y; if(intree(y,x)) return x; for(ll j = lg-1;j>=0;j--){ if(!intree(x,st[y][j])) y = st[y][j]; } return st[y][0]; } map<pll,ll> mp; ll poc[maxn]; ll kr[maxn]; void dfs3(ll u,ll par){ vis[u] =1; for(ll s : v[u]){ if(s==par) continue; dfs3(s,u); poc[u]+=poc[s]; kr[u]+=kr[s]; } mp[{u,par}] = poc[u]-kr[u]; mp[{par,u}] = poc[u]-kr[u]; } map<pll,pll> tru; int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); cin >> n >> m; for(ll i = 1;i<=m;i++){ ll x,y; cin >> x >> y; cnt[{x,y}]++; cnt[{y,x}]++; edge.pb({x,y}); g[x].pb(y); g[y].pb(x); } dfs(1,1); for(ll i = 1;i<=n;i++) if(dsu[i] == 0) dsu[i] = comp; iota(con+1,con+n+1,1); for(pll p : edge){ ll x = p.fi; ll y = p.sc; if(root(dsu[x])==root(dsu[y])) continue; tru[{x,y}] = {dsu[x],dsu[y]}; tru[{y,x}] = {dsu[x],dsu[y]}; tru[{y,x}] = {dsu[y],dsu[x]}; tru[{x,y}] = {dsu[y],dsu[x]}; v[dsu[x]].pb(dsu[y]); v[dsu[y]].pb(dsu[x]); } it = 1; fill(vis,vis+n+1,0); for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs2(i,i); for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1]; cin >> q; bool moe = 1; for(ll i = 1;i<=q;i++){ ll x,y; cin >> x >> y; x = dsu[x]; y = dsu[y]; if(x==y) continue; if(st[x][lg-1]!=st[y][lg-1]) moe = 0; poc[x]++; kr[y]++; ll z = lca(x,y); poc[z]--; kr[z]--; //cerr<<"lca: "<<x<< " "<<y<< " "<<z<<endl; } //here; //cerr<<"DSU: "<<endl; //ceri(dsu,1,n); fill(vis,vis+n+1,0); //for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" "; //cerr<<endl; for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs3(i,i); //for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" "; //cerr<<endl; for(pll p : edge){ if(cnt[p]==2) cout<<'B'; else{ if(dsu[p.fi]==dsu[p.sc]){ cout<<'B'; continue; } ll x = mp[tru[p]]; if(x==0) cout<<'B'; else if(x>0){ if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'R'; else cout<<'L'; }else{ if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'L'; else cout<<'R'; } } } cout<<endl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:144:10: warning: variable 'moe' set but not used [-Wunused-but-set-variable]
  144 |     bool moe = 1;
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...