Submission #394456

#TimeUsernameProblemLanguageResultExecution timeMemory
394456Pichon5One-Way Streets (CEOI17_oneway)C++17
0 / 100
3 ms5068 KiB
#include<bits/stdc++.h> #define lcm(a,b) (a/__gcd(a,b))*b #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long int #define vi vector<int> #define vll vector<ll> #define pb push_back #define F first #define S second #define mp make_pair using namespace std; const int MA=1e5+5; vector<pair<int,int> > G[MA]; int vis[MA]; int arc[MA]; int num=0; set<pair<int,int> >st; int puente[MA]; int depth[MA]; string res; int dp[21][MA]; void tarjan(int nodo, int ant){ num++; vis[nodo]=arc[nodo]=num; for(int it =0;it<G[nodo].size();it++){ int to=G[nodo][it].F,ind=G[nodo][it].S; if(ind==ant)continue; if(vis[to]==0){ tarjan(to,ind); if(arc[to]>vis[nodo]){ puente[ind]=1; } arc[nodo]=min(arc[nodo],arc[to]); }else{ arc[nodo]=min(arc[nodo],vis[to]); } } } vector<pair<int,int> > G2[MA]; int C[MA]; int color=0; void coloring(int nodo){ C[nodo]=color; for(int i=0;i<G[nodo].size();i++){ int to=G[nodo][i].F,ind=G[nodo][i].S; if(puente[ind] or C[to])continue; coloring(to); } } int sgt[MA]; void init(int nodo, int padre){ dp[0][nodo]=padre; for(int i=0;i<G2[nodo].size();i++){ int it=G2[nodo][i].F,ind=G2[nodo][i].S; if(it!=padre){ depth[it]=depth[nodo]+1; sgt[it]=ind; init(it,nodo); } } } void initlca(){ depth[1]=1; init(1,-1); for(int i=1;i<20;i++){ for(int l=1;l<=color;l++){ if(dp[i-1][l]==-1)continue; dp[i][l]=dp[1-1][dp[i-1][l]]; } } } int LCA(int a, int b){ if(depth[a]>depth[b])swap(a,b); //tengo que igualar alturas int dif=depth[b]-depth[a]; for(int i=0;i<20;i++){ if((1<<i)&dif){ b==dp[i][b]; } } if(a==b)return a; for(int i=19;i>=0;i--){ if(dp[i][a]==dp[i][b])continue; a=dp[i][a]; b=dp[i][b]; } return dp[0][a];//uno arribita } int main() { int n,m,p,a,b; cin>>n>>m; vector<pair<int,int> >E; for(int i=0;i<m;i++){ cin>>a>>b; G[a].pb({b,i});G[b].pb({a,i}); E.pb({a,b}); } res.assign(m,'B'); for(int i=1;i<=n;i++){ if(vis[i]==0){ tarjan(i,-1); } } for(int i=1;i<=n;i++){ if(C[i])continue; color++; coloring(i); } for(int i=0;i<m;i++){ if(puente[i]==0)continue; int A=C[E[i].F],B=C[E[i].S]; G2[A].pb({B,i}); G2[B].pb({A,i}); } initlca(); cin>>p; for(int i=0;i<p;i++){ cin>>a>>b; a=C[a],b=C[b]; if(a==b)continue; int lca=LCA(a,b); //cout<<"lca "<<a<<" "<<b<<" "<<lca<<endl; int nodo=a; while(nodo!=lca){ int ind=sgt[nodo]; if(res[ind]!='B')break; //cout<<"indice "<<ind<<endl; int pa=C[E[ind].S]; if(pa!=nodo){ res[ind]='R'; }else{ pa=C[E[ind].F]; res[ind]='L'; } nodo=pa; } nodo=b; while(nodo!=lca){ int ind=sgt[nodo]; if(res[ind]!='B')break; int pa=C[E[ind].S]; if(pa!=nodo){ res[ind]='L'; }else{ pa=C[E[ind].F]; res[ind]='R'; } nodo=pa; } } cout<<res<<endl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int it =0;it<G[nodo].size();it++){
      |                   ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void coloring(int)':
oneway.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void init(int, int)':
oneway.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<G2[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'int LCA(int, int)':
oneway.cpp:79:14: warning: statement has no effect [-Wunused-value]
   79 |             b==dp[i][b];
      |             ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...