Submission #340075

#	Time	Username	Problem	Language	Result	Execution time	Memory
340075		lukameladze	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	836 ms	78384 KiB

oneway

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2e5+5;
long long u,vv,n,m,t,lc,a[N],out[N],lv[N],b[N],fix[N],in[N],tin,p[N][20],low[N],brd[N];
vector < pair <long long, long long > > v[N];
map < pair < int, int >, int > ind;

long long pa[N];
map < pair <long long, long long > , long long> ans,brdg;
char ch[N];
int get_col(int a)
{
    if (a==pa[a]) return a;
    return pa[a]=get_col(pa[a]);
}
void dfs(int a, int b)
{
    fix[a]=1;
    tin++;
    in[a]=low[a]=tin;
    lv[a]=lv[b]+1;
    p[a][0]=b;
    for (int i=1; i<=18; i++)
    {
        p[a][i]=p[p[a][i-1]][i-1];
    }
    for (int i=0; i<v[a].size(); i++)
    {
        if (v[a][i].f==b) continue;
        if (fix[v[a][i].f])
        {
            low[a]=min(low[a],in[v[a][i].f]);
        }
        else
        {
            dfs(v[a][i].f,a);
            low[a]=min(low[a],low[v[a][i].f]);
            if (low[v[a][i].f]>in[a])
            {
                brdg[{v[a][i].f,a}]=1;
                brdg[{a,v[a][i].f}]=1;
                brd[v[a][i].s]=1;
            }
        }
    }
    out[a]=tin;
}
bool upper (int a, int b)
{
    if (in[a]<=in[b] && out[a]>=out[b]) return true;
    else return false;
}
int lca(int a, int b)
{
    if (upper(b,a)) return b;
    for (int i=18; i>=0; i--)
    {
        if (p[b][i] && !upper(p[b][i],a))
        b=p[b][i];
    }
    return p[b][0];
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>a[i]>>b[i];
        //if (a[i]==123 && b[i]==195) cout<<123<<" "<<195<<endl;
         //if (a[i]==195 && b[i]==123) cout<<123<<"   "<<195<<endl;
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
        
    }
  //  cout<<a[987-21]<<" "<<b[987-21]<<endl;
    for (int i=1; i<=n; i++)
    {
        if (!fix[i])
        {
            dfs(i,0);
        }
    }
    for (int i=1; i<=m; i++)
    {
        //if (a[i]==123 && b[i]==195) cout<<ind[{a[i],b[i]}]<<endl;
       // if (a[i]==195 && b[i]==123) cout<<ind[{a[i],b[i]}]<<endl;
        if (ind[{a[i],b[i]}]!=0)
        {
            brdg[{a[i], b[i]}]=brdg[{b[i],a[i]}]=0;
            brd[i]=0;
            brd[ind[{a[i],b[i]}]]=0;
        }
        ind[{a[i],b[i]}]=i;
        ind[{b[i],a[i]}]=i;
    }
    //cout<<brdg[{123,195}]<<endl;
    for (int i=1; i<=n; i++)
    {
        pa[i]=i;
    }
    cin>>t;
    while (t--)
    {
        cin>>u>>vv;
        lc=lca(u,vv);
        u=get_col(u);
        while (lv[u]>lv[lc])
        {
            if (brdg[{u,p[u][0]}] || brdg[{p[u][0],u}]) 
            {
                ans[{u,p[u][0]}]=1;
            }
            pa[u]=p[u][0];
            u=get_col(u);
        }
        vv=get_col(vv);
        while (lv[vv]>lv[lc])
        {
            if (brdg[{vv,p[vv][0]}] || brdg[{p[vv][0],vv}]) ans[{p[vv][0],vv}]=1;
            pa[vv]=p[vv][0];
            vv=get_col(vv);
        }
    }
    for (int i=1; i<=m; i++)
    {
        if (!brd[i]) 
        {
            cout<<"B";
            continue;
        }
        if (ans[{a[i],b[i]}]==1) cout<<"R";
        else if (ans[{b[i],a[i]}]==1) cout<<"L";
        else cout<<"B";
    }
}

Compilation message (stderr)

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

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