Submission #1109440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109440		simona1230	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	125 ms	44480 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
int n,m;
vector<int> v[200001],id[200001];
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        id[x].push_back(i);
        id[y].push_back(-i);
    }
}

int bridge[200001];
int t,in[200001];
int low[200001];

void dfs(int i,int p)
{
    low[i]=in[i]=++t;
    //cout<<i<<" "<<in[i]<<endl;

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        if(!in[nb])
        {
            dfs(nb,i);
            //cout<<i<<" > "<<nb<<" "<<low[nb]<<endl;
            low[i]=min(low[i],low[nb]);
            if(low[nb]>in[i])bridge[abs(id[i][j])]=1;
        }
        else low[i]=min(low[i],in[nb]);
    }
}

int num,c[200001];
vector<int> g[200001],idx[200001];

void dfs1(int i)
{
    c[i]=num;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(!c[nb]&&!bridge[abs(id[i][j])])
        {
            dfs1(nb);
        }
        else if(c[nb]&&c[i]!=c[nb])
        {
            g[c[nb]].push_back(c[i]);
            g[c[i]].push_back(c[nb]);
            idx[c[nb]].push_back(-id[i][j]);
            idx[c[i]].push_back(id[i][j]);
        }
    }
}


int q;
int d[200001];
int sz[200001];
char ans[200001];
int hey[200001];
void dfs2(int i,int p)
{
    hey[i]=1;
    sz[i]=d[i];
    for(int j=0;j<g[i].size();j++)
    {
        int nb=g[i][j];
        if(p==nb)continue;

        dfs2(nb,i);
        if(sz[nb]==0)ans[abs(idx[i][j])]='B';
        else if(sz[nb]>0&&idx[i][j]>0||sz[nb]<0&&idx[i][j]<0)
            ans[abs(idx[i][j])]='L';
        else ans[abs(idx[i][j])]='R';
        sz[i]+=sz[nb];
    }
}

void solve()
{
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,y;
        cin>>x>>y;
        d[c[x]]++;
        d[c[y]]--;
    }

   /*for(int i=1;i<=n;i++)
        cout<<c[i]<<" ";
    cout<<endl;*/

    for(int i=1;i<=num;i++)
        if(!hey[i])dfs2(i,-1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	read();
	for(int i=1;i<=n;i++)
        if(!in[i])dfs(i,-1);
    for(int i=1;i<=n;i++)
    {
        if(!c[i])
        {
            num++;
            dfs1(i);
        }
    }
    for(int i=1;i<=m;i++)
        ans[i]='B';

    solve();

    for(int i=1;i<=m;i++)
        cout<<ans[i];
    cout<<endl;
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j=0;j<g[i].size();j++)
      |                 ~^~~~~~~~~~~~
oneway.cpp:85:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |         else if(sz[nb]>0&&idx[i][j]>0||sz[nb]<0&&idx[i][j]<0)
      |                 ~~~~~~~~^~~~~~~~~~~~~

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