Submission #394548

#TimeUsernameProblemLanguageResultExecution timeMemory
394548Pichon5One-Way Streets (CEOI17_oneway)C++17
0 / 100
10 ms14056 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=1e+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[22][MA]; vi P; 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,int d){ depth[nodo]=d; 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){ sgt[it]=ind; init(it,nodo,d+1); } } } void initlca(){ memset(depth,-1,sizeof(depth)); memset(dp,-1,sizeof(dp)); for(int i=1;i<=color;i++){ if(depth[i]==-1){ init(i,-1,0); } } for(int i=1;i<=18;i++){ for(int l=1;l<=MA;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); int dif=depth[b]-depth[a]; for(int i=18;i>=0;i--){ if((1<<i)&dif){ b=dp[i][b]; } } if(a==b)return a; for(int i=18;i>=0;i--){ if(dp[i][a]==dp[i][b])continue; a=dp[i][a]; b=dp[i][b]; } return dp[0][a]; } 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); int nodo=a; while(nodo!=lca){ int ind=sgt[nodo]; //if(res[ind]!='B')break; int pa=C[E[ind].S]; if(pa!=nodo){ res[ind]='R'; }else{ res[ind]='L'; } nodo=dp[0][nodo]; } 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{ res[ind]='R'; } nodo=dp[0][nodo]; } } cout<<res<<endl; return 0; } /* 20 23 1 15 1 16 15 16 6 5 5 16 15 5 6 10 18 20 19 18 3 4 3 10 17 20 19 20 13 14 11 9 11 12 12 2 2 11 9 8 7 8 9 10 6 8 12 13 7 13 4 2 7 16 3 17 18 17 19 8 10 10 8 */

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:26: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]
   26 |     for(int it =0;it<G[nodo].size();it++){
      |                   ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void coloring(int)':
oneway.cpp:45: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]
   45 |     for(int i=0;i<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void init(int, int, int)':
oneway.cpp:55: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]
   55 |     for(int i=0;i<G2[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void initlca()':
oneway.cpp:74:25: warning: iteration 99999 invokes undefined behavior [-Waggressive-loop-optimizations]
   74 |             if(dp[i-1][l]==-1)continue;
      |                ~~~~~~~~~^
oneway.cpp:73:22: note: within this loop
   73 |         for(int l=1;l<=MA;l++){
      |                     ~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...