Submission #577484

#	Time	Username	Problem	Language	Result	Execution time	Memory
577484		vladislav11	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	212 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

int n, m, p, ttime;
vector< vector< pair<int,int> > > grp;
vector< pair<int,int> > ribs;

vector< pair<int,int> > a;
vector<int> used, tin, tup, brg;

void dfs_time ( int v, int pind )
{
    used[v] = 1;
    tin[v] = tup[v] = ttime++;

    for ( auto& [to,ind] : grp[v] )
    if ( ind != pind )
    {
        if ( !used[to] )
        {
            dfs_time( to, ind );

            if ( tup[to] > tin[v] )
                brg[ind] = 1;

            tup[v] = min( tup[v], tup[to] );
        }
        else
            tup[v] = min( tup[v], tin[to] );
    }
}

vector< vector<int> > tree;
vector<int> color;
int ccol;

void dfs_color ( int v, int cl )
{
    color[v] = cl;

    for ( auto& [to,ind] : grp[v] )
    if ( !brg[ind] && !color[to] )
        dfs_color( to, cl );
}

vector< vector<int> > up;
vector<int> h, ctin, ctout;

void dfs_up ( int v, int p )
{
    ctin[v] = ttime++;

    up[v][0] = p;

    for ( int i=1; i<21; i++ )
    if ( up[v][i-1] != -1 )
        up[v][i] = up[ up[v][i-1] ][i-1];

    for ( auto& to : tree[v] )
    if ( to != p )
    {
        h[to] = h[v] + 1;

        dfs_up( to, v );
    }

    ctout[v] = ttime++;
}

int lca ( int u, int v )
{
    if ( u == v )
        return u;

    if ( h[u] > h[v] )
        swap( u, v );

    for ( int i=20; i>=0; i-- )
    if ( up[v][i] != -1 )
    {
        int to = up[v][i];

        if ( ctin[to] <= ctin[u] && ctout[to] >= ctout[u] )
            continue;

        v = to;
    }

    return up[v][0];
}

vector<int> rib_dir;

int dfs_dir ( int v, int p )
{
    for ( auto& to : tree[v] )
    if ( to != p )
        rib_dir[v] += dfs_dir( to, v );

    return rib_dir[v];
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    grp.assign( n+1, vector< pair<int,int> >() );

    for ( int i=0; i<m; i++ )
    {
        int u, v;
        cin >> u >> v;

        grp[u].push_back({ v, i });
        grp[v].push_back({ u, i });

        ribs.push_back({ u, v });
    }

    cin >> p;

    a.resize( p );

    for ( auto& [x,y] : a )
        cin >> x >> y;

    used = tin = tup = vector<int>( n+1, 0 );
    brg.assign( m, 0 );

    for ( int i=1; i<=n; i++ )
    if ( !used[i] )
        dfs_time( i, -1 );

    color.assign( n+1, 0 );

    for ( int i=1; i<=n; i++ )
    if ( !color[i] )
        dfs_color( i, ++ccol );

    /*for ( int i=1; i<=n; i++ )
        cout << color[i] << ' ';
    cout << '\n';*/

    tree.assign( ccol+1, vector<int>() );

    for ( int i=1; i<=n; i++ )
    for ( auto& [to,ind] : grp[i] )
    if ( i < to && brg[ind] )
    {
        tree[ color[i] ].push_back( color[to] );
        tree[ color[to] ].push_back( color[i] );
    }

    /*cout << "tree:\n";
    for ( int i=1; i<=ccol; i++ )
    {
        cout << i << ": ";

        for ( auto& to : tree[i] )
            cout << to << ' ';
        cout << '\n';
    }*/

    up.assign( ccol+1, vector<int>( 21, -1 ) );
    h = ctin = ctout = vector<int>( ccol+1, 0 );

    dfs_up( 1, -1 );

    rib_dir.assign( ccol+1, 0 );

    for ( auto& [x,y] : a )
    {
        x = color[x];
        y = color[y];

        if ( x == y )
            continue;

        int w = lca( x, y );

        rib_dir[x]++;
        rib_dir[w]--;

        rib_dir[y]--;
        rib_dir[w]++;
    }

    dfs_dir( 1, -1 );

    for ( auto& [x,y] : ribs )
    {
        if ( color[x] == color[y] )
            cout << 'B';

        else
        {
            x = color[x];
            y = color[y];

            int w = h[x] < h[y] ? y : x;

            if ( rib_dir[w] == -1 )
                cout << ( w == y ? 'R' : 'L' );

            else if ( rib_dir[w] == 1 )
                cout << ( w == y ? 'L' : 'R' );

            else
                cout << 'B';
        }
    }

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs_time(int, int)':
oneway.cpp:17:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for ( auto& [to,ind] : grp[v] )
      |                 ^
oneway.cpp: In function 'void dfs_color(int, int)':
oneway.cpp:42:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for ( auto& [to,ind] : grp[v] )
      |                 ^
oneway.cpp: In function 'int main()':
oneway.cpp:128:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for ( auto& [x,y] : a )
      |                 ^
oneway.cpp:151:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |     for ( auto& [to,ind] : grp[i] )
      |                 ^
oneway.cpp:175:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  175 |     for ( auto& [x,y] : a )
      |                 ^
oneway.cpp:194:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  194 |     for ( auto& [x,y] : ribs )
      |                 ^

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