Submission #66407

#	Time	Username	Problem	Language	Result	Execution time	Memory
66407		Vahan	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	492 ms	65052 KiB

oneway

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,k,u[200000],fup[200000],tin[200000],timer;
vector<pair<int,int> > g[200000],br,tr[200000];
vector<pair<int,pair<int,int > > > cuc;
char pa[200000];
int sz[200000],par[2000000],uxx[200000],ux[200000],ind[200000],parent[200000][22],tiin[200000],tout[200000],pp[200000],h[200000];
void setcreate(int a)
{
    sz[a]=1;
    par[a]=a;
}
int findparent(int a)
{
    if(par[a]==a)
        return a;
    return par[a]=findparent(par[a]);
}
void setunion(int a,int b)
{
    a=findparent(a);
    b=findparent(b);
    if(a==b)
        return;
    if(sz[a]>=sz[b])
    {
        par[b]=a;
        sz[a]+=sz[b];
    }
    if(sz[b]>sz[a])
    {
        par[a]=b;
        sz[b]+=sz[a];
    }
}
void dfs(int v,int p)
{
    u[v]=1;
    fup[v]=tin[v]=timer++;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        int ham=g[v][i].second;
        if(to==v)
        {
            pa[ham]='B';
            continue;
        }
        if(p==to)
            continue;
        if(u[to]==1)
        {
            fup[v]=min(fup[v],tin[to]);
            pa[ham]='B';
            setunion(v,to);
        }
        else
        {
            dfs(to,v);
            fup[v]=min(fup[v],fup[to]);
            if(fup[to]>tin[v])
                br.push_back(make_pair(v,i));
            else
            {
                pa[ham]='B';
                setunion(v,to);
            }
        }
    }
}
void dfs1(int v,int p)
{
    tiin[v]=timer++;
    u[v]=1;
    parent[v][0]=p;
    for(int i=1;i<=20;i++)
            parent[v][i]=parent[parent[v][i-1]][i-1];
    for(int i=0;i<tr[v].size();i++)
    {
        int to=tr[v][i].first;
        int ham=tr[v][i].second;
        if(u[to]==1)
            continue;
        pp[to]=ham;
        h[to]=h[v]+1;
        dfs1(to,v);
    }
    tout[v]=timer++;
}

bool upper (int a, int b) {
	return tiin[a] <= tiin[b] && tout[a] >= tout[b];
}
int lca (int a, int b) {
	if (upper (a, b))  return a;
	if (upper (b, a))  return b;
	for (int i=20; i>=0; --i)
		if (! upper (parent[a][i], b))
			a = parent[a][i];
	return parent[a][0];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        uxx[i]=a;
        g[a].push_back(make_pair(b,i));
        g[b].push_back(make_pair(a,i));
    }
    for(int i=1;i<=n;i++)
        setcreate(i);
    for(int i=1;i<=n;i++)
    {
        if(u[i]==0)
            dfs(i,0);
    }
    for(int i=1;i<=n;i++)
        ind[i]=findparent(i);
    for(int i=0;i<br.size();i++)
    {
        int a=br[i].first,b=g[a][br[i].second].first,ham=g[a][br[i].second].second;
        uxx[ham]=ind[uxx[ham]];
        tr[ind[a]].push_back(make_pair(ind[b],ham));
        tr[ind[b]].push_back(make_pair(ind[a],ham));
    }
    for(int i=1;i<=n;i++)
        u[ind[i]]=0;
    timer=0;
    for(int i=1;i<=n;i++)
    {
        if(u[ind[i]]==0)
            dfs1(ind[i],ind[i]);
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int a,b;
        cin>>a>>b;
        a=ind[a];
        b=ind[b];
        if(a==b)
            continue;
        int c=lca(a,b);
        cuc.push_back(make_pair(h[c],make_pair(a,b)));
    }
    sort(cuc.begin(),cuc.end());
    for(int i=0;i<cuc.size();i++)
    {
        int a=cuc[i].second.first,b=cuc[i].second.second;
        int c=lca(a,b);
        int e=a;
        while(e!=c)
        {
            int ee=parent[e][0];
            if(pa[pp[e]]=='R' || pa[pp[e]]=='L')
                break;
            if(uxx[pp[e]]==e)
                pa[pp[e]]='R';
            else
                pa[pp[e]]='L';
            e=ee;
        }
        e=b;
        while(e!=c)
        {
            int ee=parent[e][0];
            if(pa[pp[e]]=='R' || pa[pp[e]]=='L')
                break;
            if(uxx[pp[e]]==e)
                pa[pp[e]]='L';
            else
                pa[pp[e]]='R';
            e=ee;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(pa[i]==0)
            pa[i]='B';
        cout<<pa[i];
    }
    return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<br.size();i++)
                 ~^~~~~~~~~~
oneway.cpp:152:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cuc.size();i++)
                 ~^~~~~~~~~~~

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