Submission #735212

#TimeUsernameProblemLanguageResultExecution timeMemory
735212MasterTasterOne-Way Streets (CEOI17_oneway)C++14
0 / 100
5 ms5460 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 100010 #define pii pair<int, int> #define xx first #define yy second #define pb push_back using namespace std; int n, m, low[MAXN], tin[MAXN], tout[MAXN], timer, col[MAXN], logg; vector<int> g[MAXN], gg[MAXN]; vector<pii> bridge, grane; vector<pair<int, pii> >svi; bool bio[MAXN]; map<pii, bool> b; map<pii, int> dir; int up[MAXN][25]; void dfs(int u, int p) { bio[u]=true; tin[u]=low[u]=timer++; for (auto v:g[u]) { if (v==p) continue; if (bio[v]) low[u]=min(low[u], tin[v]); else { dfs(v, u); low[u]=min(low[u], low[v]); if (low[v]>tin[u]) { /*cout<<u<<" bridge "<<v<<endl;*/ bridge.pb({u, v}); b[{u, v}]=b[{v, u}]=true; } } } } void dfs2(int u, int c) { bio[u]=true; col[u]=c; for (auto v:g[u]) { if (!bio[v] && !b[{u, v}]) dfs2(v, c); } } void dfs3(int u, int p) { ///cout<<u<<" dfs3 "<<timer+1<<endl; bio[u]=true; tin[u]=++timer; up[u][0]=p; for (int i=1; i<=logg; i++) up[u][i]=up[up[u][i-1]][i-1]; for (auto v:gg[u]) if (!bio[v]) dfs3(v, u); tout[u]=++timer; } bool isanc(int u, int v) ///is u ancestor of v? { return (tin[u]<=tin[v] && tout[u]>=tout[v]); } int lca(int u, int v) { ///cout<<tin[u]<<" "<<tout[u]<<" "<<tin[v]<<" "<<tout[v]<<endl; if (isanc(u, v)) return u; if (isanc(v, u)) return v; for (int i=logg; i>=0; i--) { if (!isanc(up[u][i], v)) u=up[u][i]; } return up[u][0]; } int main() { cin>>n>>m; for (int i=0; i<m; i++) { int u, v; cin>>u>>v; grane.pb({u, v}); g[u].pb(v); g[v].pb(u); } for (int i=1; i<=n; i++) { if (!bio[i]) dfs(i, -1); } for (int i=1; i<=n; i++) bio[i]=false; int cc=1; for (int i=1; i<=n; i++) { if (!bio[i]) dfs2(i, cc++); } //for (int i=1; i<=n; i++) cout<<col[i]<<" "; //cout<<endl; for (int i=0; i<bridge.size(); i++) { int u=col[bridge[i].xx], v=col[bridge[i].yy]; ///cout<<"povezujem "<<u<<" "<<v<<endl; gg[u].pb(v); gg[v].pb(u); } for (int i=1; i<cc; i++) bio[i]=false; logg=ceil(log2(n)); timer=0; for (int i=1; i<cc; i++) { if (!bio[i]) dfs3(i, i); } int pp; cin>>pp; while (pp--) { int x, y; cin>>x>>y; x=col[x]; y=col[y]; int xy=lca(x, y); svi.pb({tin[xy], {x, y}}); } sort(svi.begin(), svi.end()); for (auto par:svi) { int x=par.yy.xx; int y=par.yy.yy; if (x==y) continue; int xy=lca(x, y); //cout<<x<<" "<<y<<" "<<xy<<endl; while (x!=xy) { int p=up[x][0]; if (dir[{x, p}]) break; //cout<<x<<" xp "<<p<<endl; dir[{x, p}]=1; dir[{p, x}]=2; x=p; } while (y!=xy) { int p=up[y][0]; if (dir[{y, p}]) break; //cout<<y<<" yp "<<p<<endl; dir[{y, p}]=2; dir[{p, y}]=1; y=p; } } for (int i=0; i<m; i++) { int u, v; u=grane[i].xx; v=grane[i].yy; if (!b[{u, v}]) { cout<<'B'; continue; } u=col[u]; v=col[v]; //cout<<u<<" uv "<<v<<endl; if (dir[{u, v}]==1) { cout<<'R'; } else if (dir[{u, v}]==2) { cout<<'L'; } else { cout<<'B'; } } }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i=0; i<bridge.size(); i++)
      |                   ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...