Submission #394550

#	Time	Username	Problem	Language	Result	Execution time	Memory
394550		Pichon5	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3080 ms	14064 KiB

oneway

#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';
                pa=C[E[ind].F];
            }
            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;
}
/*
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++){
      |                     ~^~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40