Submission #340082

#	Time	Username	Problem	Language	Result	Execution time	Memory
340082		wildturtle	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	487 ms	43376 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,t,q;
long long disc[500005],low[500005],A[500005],B[500005],C[500005],D[500005],E[500005];
long long P[22][500005],br[500005],ans[500005],in[500005],out[500005];
vector < pair <long long , long long > > v[500005];
void dfs(long long x,long long y) {
    t++;
    disc[x]=t; low[x]=t;
    for(long long i=0;i<v[x].size();i++) {
        if(v[x][i].first==x) continue;
        if(disc[v[x][i].first]==0) {
            P[0][v[x][i].first]=x; D[v[x][i].first]=D[x]+1; E[v[x][i].first]=v[x][i].second;
            dfs(v[x][i].first,x);
            low[x]=min(low[x],low[v[x][i].first]);
            if(low[v[x][i].first]>disc[x]) br[v[x][i].first]=1;
        }
        else {
            if(P[0][v[x][i].first]==x) br[v[x][i].first]=0;
            if(v[x][i].first!=P[0][x]) low[x]=min(low[x],disc[v[x][i].first]);
        }
    }
}
int LCA(int u, int v) {
    if(D[u]<D[v]) swap(u, v);
    for(int k = 18 - 1; ~k; k--)
        if (D[P[k][u]]>=D[v]) u=P[k][u];
    if(u==v) return u;
    for (int k=18-1; ~k; k--)
        if(P[k][u]!=P[k][v]) { u=P[k][u]; v=P[k][v]; }
    return P[0][u];
}
long long get_col(long long x) {
  if (C[x] == x)
    return x;
  C[x] = get_col(C[x]);
  return C[x];
}
int main() {
    cin>>n>>m;
    for(long long i=0;i<m;i++) {
        cin>>A[i]>>B[i];
        v[A[i]].push_back({B[i],i});
        v[B[i]].push_back({A[i],i});
    }
    for(long long i=1;i<=n;i++) {
        if(disc[i]==0) dfs(i,0);
    }
    ////
    /*
    for(long long i=1;i<=n;i++) {
        cout<<E[i]<<" ";
    }
    cout<<endl;
    */////
    for(long long i=1;i<18;i++) {
        for(long long j=1;j<=n;j++) {
            P[i][j]=P[i-1][P[i-1][j]];
        }
    }
    for(long long i=1;i<=n;i++) {
        C[i]=i;
    }
    cin>>q;
    for(long long i=1;i<=q;i++) {
        cin>>a>>b;
        l=LCA(a,b);
        //cout<<l<<" ";
        a=get_col(a); b=get_col(b);
        //cout<<b<<" ";
        while(D[a]>D[l]) {
            if(br[a]==1) ans[E[a]]=-1;
            C[a]=P[0][a];
            a=get_col(a);
        }
        while(D[b]>D[l]) {
            if(br[b]==1) ans[E[b]]=1;
            C[b]=P[0][b];
            b=get_col(b);
        }
    }
    //cout<<endl;
    for(long long i=1;i<=n;i++) {
        if(br[i]==1 && B[E[i]]!=i) ans[E[i]]*=-1;
    }
    for(long long i=0;i<m;i++) {
        if(ans[i]==0) cout<<"B";
        else if(ans[i]==1) cout<<"R";
        else cout<<"L";
    }
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(long long int, long long int)':
oneway.cpp:10:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(long long i=0;i<v[x].size();i++) {
      |                       ~^~~~~~~~~~~~

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