Submission #394151

#TimeUsernameProblemLanguageResultExecution timeMemory
394151Pichon5One-Way Streets (CEOI17_oneway)C++17
0 / 100
3 ms4940 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 //salida rapida "\n" //DECIMALES fixed<<sp(n)<<x<<endl; //gcd(a,b)= ax + by //gcd(a,b)=gcd(a-b,b) a>=b //lCB x&-x //set.erase(it) - ersases the element present at the required index//auto it = s.find(element) //set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end() //set.lower_bound(element) - iterator pointing to element greater than or equal to the given element //set.upper_bound(element) - iterator pointing to element greater than the given element // | ^ //__builtin_popcount(x) 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]; string res; 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){ cout<<nodo<<endl; 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 B[MA]; void dfs(int nodo, int padre){ for(int i=0;i<G2[nodo].size();i++){ int to=G2[nodo][i].F,ind=G2[nodo][i].S; if(to==padre)continue; B[to]=ind; dfs(to,nodo); } } 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]; if(A==B)continue; //cout<<"UNO "<<A<<" "<<B<<endl; G2[A].pb({B,i}); G2[B].pb({A,i}); } cin>>p; for(int i=0;i<p;i++){ cin>>a>>b; a=C[a],b=C[b]; if(a==b)continue; dfs(a,-1); int nodo=b; while(nodo!=a){ int ind=B[nodo]; int from=C[E[ind].F]; if(from==nodo){ from=C[E[ind].S]; res[ind]='L'; }else{ res[ind]='R'; } nodo=from; } } cout<<res<<endl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:35: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]
   35 |     for(int it =0;it<G[nodo].size();it++){
      |                   ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void coloring(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<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:63: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]
   63 |     for(int i=0;i<G2[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...