oj.uz

Submission #962835

# Submission time Handle Problem Language Result Execution time Memory
962835 2024-04-14T08:48:59 Z LucaIlie One-Way Streets (CEOI17_oneway) C++17
100 / 100
 484 ms 145984 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v;

    bool operator == ( const edge &x ) const {
        return (u == x.u && v == x.v) || (u == x.v && u == x.u);
    }

    bool operator != ( const edge &x ) const {
        return !(edge{ u, v } == x);
    }
};

const int none = 0;
const int up = 1;
const int down = 2;
const int MAX_N = 3e5;
const int MAX_LOG_N = 18;
const int MAX_M = 3e5;
bool vis[MAX_N + 1], isInBiconex[MAX_N + 1];
int depth[MAX_N + 1], climbDepth[MAX_N + 1], countEdges[MAX_N + 1], vertexArt[MAX_N + 1], vertexBic[MAX_N + 1], biconex[MAX_N + 1], depthArb[MAX_N + 1], parent[MAX_LOG_N + 1][MAX_N + 1], art[MAX_N + 1], dir[MAX_N + 1];
vector<int> adj[MAX_N + 1], arbAdj[MAX_N + 1];
edge edges[MAX_M];
vector<int> articulation;
vector<vector<int>> biconexe;
unordered_map<int, bool> direction[MAX_N + 1];

vector<edge> edgeStack;
unordered_map<int, int> frecvEdges[MAX_N + 1];
void findBiconexe( int u, int p ) {
    vis[u] = true;
    depth[u] = depth[p] + 1;
    climbDepth[u] = depth[u];
    int c = 0;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;

        if ( vis[v] ) {
            if ( depth[v] < depth[u] ) {
                edgeStack.push_back( { u, v } );
                climbDepth[u] = min( climbDepth[u], depth[v] );
            }
        } else {
            edgeStack.push_back( { u, v } );
            c++;
            findBiconexe( v, u );
            climbDepth[u] =min( climbDepth[u], climbDepth[v] );

            if ( climbDepth[v] >= depth[u] ) {
                biconexe.push_back( {} );
                if ( p != 0 )
                    articulation.push_back( u );

                edge e;
                do {
                    e = edgeStack.back();
                    edgeStack.pop_back();
                    countEdges[biconexe.size() - 1] += frecvEdges[e.u][e.v] + frecvEdges[e.v][e.u];
                    if ( !isInBiconex[e.u] ) {
                        biconexe.back().push_back( e.u );
                        isInBiconex[e.u] = true;
                    }
                    if ( !isInBiconex[e.v] ) {
                        biconexe.back().push_back( e.v );
                        isInBiconex[e.v] = true;
                    }
                } while ( e != edge{ u, v } );

                for ( int w: biconexe.back() )
                    isInBiconex[w] = false;
            }
        }
    }

    if ( p == 0 && c > 1 )
        articulation.push_back( u );
}

void dfs( int u, int p ) {
    vis[u] = true;
    parent[0][u] = p;
    depthArb[u] = depthArb[p] + 1;
    for ( int v: arbAdj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

void initLca( int n ) {
    for ( int p = 1; p <= MAX_LOG_N; p++ ) {
        for ( int v = 1; v <= n; v++ )
            parent[p][v] = parent[p - 1][parent[p - 1][v]];
    }
}

int lca( int u, int v ) {
    if ( depthArb[u] > depthArb[v] )
        swap( u, v );

    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( depthArb[parent[p][v]] >= depthArb[u] )
            v = parent[p][v];
    }


    if ( u == v )
        return u;

    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( parent[p][u] != parent[p][v] ) {
            u = parent[p][u];
            v = parent[p][v];
        }
    }

    return parent[0][u];
}

int updateUp[MAX_N + 1], dpUp[MAX_N + 1], updateDown[MAX_N + 1], dpDown[MAX_N + 1];
void calcUpDown( int u, int p ) {
    vis[u] = true;
    dpUp[u] = updateUp[u];
    dpDown[u] = updateDown[u];
    for ( int v: arbAdj[u] ) {
        if ( v == p )
            continue;
        calcUpDown( v, u );
        dpUp[u] += dpUp[v];
        dpDown[u] += dpDown[v];
    }
    if ( dpUp[u] > 0 )
        dir[u] = up;
    if ( dpDown[u] > 0 )
        dir[u] = down;

    //printf( "%d %d %d\n", u, dpDown[u], dpUp[u] );
}

int main() {
    int n, m;

    cin >> n >> m;
    for  ( int i = 0; i < m; i++ ) {
        int u, v;
        cin >> u >> v;
        edges[i] = { u, v };
        if ( u == v )
            continue;

        adj[u].push_back( v );
        adj[v].push_back( u );
        if ( u > v )
            swap( u, v );
        frecvEdges[u][v]++;
    }

    for ( int v = 1; v <= n; v++ ) {
        if ( !vis[v] )
            findBiconexe( v, 0 );
    }

    /*int i = 0;
    for ( vector<int> b: biconexe ) {
        for ( int v: b )
            cout << v << " ";
        cout << "\n";
        cout << countEdges[i++] << "\n";
    }
    for ( int v: articulation )
        cout << v << " ";
    cout << "\n";*/

    int vert = 0;
    for ( int v: articulation ) {
        vertexArt[v] = ++vert;
        art[vert] = v;
    }
    for ( int i = 0; i < biconexe.size(); i++ ) {
        vertexBic[i] = ++vert;
        for ( int v: biconexe[i] ) {
            if ( vertexArt[v] ) {
                arbAdj[vertexArt[v]].push_back( vertexBic[i] );
                arbAdj[vertexBic[i]].push_back( vertexArt[v] );
                //printf( "edgearb %d %d %d %d\n", v, i, vertexArt[v], vertexBic[i] );
            } else
                biconex[v] = i;
        }
    }

    for ( int v = 1; v <= n; v++ )
        vis[v] = false;
    for ( int v = 1; v <= n; v++ ) {
        if ( !vis[v] )
            dfs( v, 0 );
    }

    initLca( vert );
    for ( int v = 1; v <= vert; v++ )
        dir[v] = none;

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

        u = (vertexArt[u] ? vertexArt[u] : vertexBic[biconex[u]]);
        v = (vertexArt[v] ? vertexArt[v] : vertexBic[biconex[v]]);
        int l = lca( u, v );
        //printf( "%d %d %d\n", u, v,  l );
        //printf( "%d %d\n", u, v );

        if ( u == v && countEdges[u - 1 - articulation.size()] == 1 )
            direction[a][b] = 1;

        if ( k <= 100 ) {
            while ( depthArb[u] > depthArb[v] ) {
                if ( u > articulation.size() )
                    dir[u] = up;
                //printf( "%d\n", u );
                u = parent[0][u];
            }
            while ( depthArb[v] > depthArb[u] ) {
                if ( v > articulation.size() )
                    dir[v] = down;
                // printf( "%d\n", v );
                v = parent[0][v];
            }
            while ( u != v ) {
                //printf( "%d\n%d\n", u, v );
                if ( u > articulation.size())
                    dir[u] = up;
                u = parent[0][u];
                if ( v > articulation.size())
                    dir[v] = down;
                v = parent[0][v];
            }
        } else {
            updateUp[u]++;
            updateUp[parent[0][l]]--;
            updateDown[v]++;
            updateDown[parent[0][l]]--;
        }
    }

    for ( int v = 1; v <= n; v++ )
        vis[v] = false;
    for ( int v = 1; v <= n; v++ ) {
        if ( !vis[v] )
            calcUpDown( v, 0 );
    }

    for ( int i = 0; i < biconexe.size(); i++ ) {
        int v = vertexBic[i];
        if ( countEdges[i] != 1 )
            continue;

        int a = biconexe[i][0], b = biconexe[i][1];
        //printf( "ba %d %d %d\n", v, a, b );
        if ( a == art[parent[0][v]] )
            swap( a, b );

        if ( dir[v] == up )
            direction[a][b] = 1;
        else if ( dir[v] == down )
            direction[b][a] = 1;
    }

    string ans = "";
    for ( int i = 0; i < m; i++ ) {
        int u = edges[i].u, v = edges[i].v;
        if ( direction[u][v] )
            ans += 'R';
        else if ( direction[v][u] )
            ans += 'L';
        else
            ans += 'B';
        //cout << i << " " << ans.back() << "\n";
    }

    cout << ans;

    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:183:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for ( int i = 0; i < biconexe.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~
oneway.cpp:224:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |                 if ( u > articulation.size() )
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:230:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |                 if ( v > articulation.size() )
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:237:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |                 if ( u > articulation.size())
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:240:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |                 if ( v > articulation.size())
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:259:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |     for ( int i = 0; i < biconexe.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80468 KB Output is correct
2 Correct 17 ms 80472 KB Output is correct
3 Correct 16 ms 80728 KB Output is correct
4 Correct 18 ms 80988 KB Output is correct
5 Correct 17 ms 80984 KB Output is correct
6 Correct 17 ms 80728 KB Output is correct
7 Correct 22 ms 80988 KB Output is correct
8 Correct 18 ms 80988 KB Output is correct
9 Correct 17 ms 80808 KB Output is correct
10 Correct 20 ms 80732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80468 KB Output is correct
2 Correct 17 ms 80472 KB Output is correct
3 Correct 16 ms 80728 KB Output is correct
4 Correct 18 ms 80988 KB Output is correct
5 Correct 17 ms 80984 KB Output is correct
6 Correct 17 ms 80728 KB Output is correct
7 Correct 22 ms 80988 KB Output is correct
8 Correct 18 ms 80988 KB Output is correct
9 Correct 17 ms 80808 KB Output is correct
10 Correct 20 ms 80732 KB Output is correct
11 Correct 163 ms 104024 KB Output is correct
12 Correct 146 ms 107032 KB Output is correct
13 Correct 216 ms 113332 KB Output is correct
14 Correct 240 ms 121856 KB Output is correct
15 Correct 251 ms 124016 KB Output is correct
16 Correct 300 ms 132784 KB Output is correct
17 Correct 262 ms 136068 KB Output is correct
18 Correct 297 ms 132760 KB Output is correct
19 Correct 259 ms 139076 KB Output is correct
20 Correct 161 ms 111404 KB Output is correct
21 Correct 155 ms 110164 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80468 KB Output is correct
2 Correct 17 ms 80472 KB Output is correct
3 Correct 16 ms 80728 KB Output is correct
4 Correct 18 ms 80988 KB Output is correct
5 Correct 17 ms 80984 KB Output is correct
6 Correct 17 ms 80728 KB Output is correct
7 Correct 22 ms 80988 KB Output is correct
8 Correct 18 ms 80988 KB Output is correct
9 Correct 17 ms 80808 KB Output is correct
10 Correct 20 ms 80732 KB Output is correct
11 Correct 163 ms 104024 KB Output is correct
12 Correct 146 ms 107032 KB Output is correct
13 Correct 216 ms 113332 KB Output is correct
14 Correct 240 ms 121856 KB Output is correct
15 Correct 251 ms 124016 KB Output is correct
16 Correct 300 ms 132784 KB Output is correct
17 Correct 262 ms 136068 KB Output is correct
18 Correct 297 ms 132760 KB Output is correct
19 Correct 259 ms 139076 KB Output is correct
20 Correct 161 ms 111404 KB Output is correct
21 Correct 155 ms 110164 KB Output is correct
22 Correct 379 ms 137852 KB Output is correct
23 Correct 484 ms 134628 KB Output is correct
24 Correct 439 ms 133804 KB Output is correct
25 Correct 406 ms 145984 KB Output is correct
26 Correct 372 ms 137568 KB Output is correct
27 Correct 422 ms 135196 KB Output is correct
28 Correct 85 ms 88512 KB Output is correct
29 Correct 208 ms 115400 KB Output is correct
30 Correct 196 ms 115720 KB Output is correct
31 Correct 221 ms 116344 KB Output is correct
32 Correct 287 ms 125552 KB Output is correct