Submission #44655

#	Time	Username	Problem	Language	Result	Execution time	Memory
44655		bogdan10bos	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	251 ms	57428 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

pii edge[100005];
int N, M, K;
int node[100005];
char r[100005];

namespace BiconnexGraph
{
    int h[100005], low[100005], f[100005];
    bool vis[100005], crit[100005];
    vector<int> edg[100005];

    void addEdge(int id)
    {
        int x = edge[id].first, y = edge[id].second;
        edg[x].push_back(id);
        edg[y].push_back(id);
    }

    int F(int x)
    {
        if(f[x] == x)   return x;
        return f[x] = F(f[x]);
    }

    void DFS(int nod, int id)
    {
        int fth = edge[id].first ^ edge[id].second ^ nod;
        h[nod] = h[fth] + 1;
        low[nod] = h[nod];

        for(auto e: edg[nod])
        {
            if(e == id)   continue;

            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(low[nxt] != 0)
            {
                low[nod] = min(low[nod], low[nxt]);
                continue;
            }

            DFS(nxt, e);
            low[nod] = min(low[nod], low[nxt]);

            if(low[nxt] > h[nod])
                crit[e] = 1;
        }
    }

    void unite(int x, int y)
    {
        if(F(x) == F(y))    return;
        f[F(y)] = F(x);
    }

    void uniteDFS(int nod)
    {
        if(vis[nod])    return;
        vis[nod] = 1;
        for(auto e: edg[nod])
        {
            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(!crit[e])
            {
                uniteDFS(nxt);
                unite(nod, nxt);
            }
        }
    }

    void compressGraph()
    {
        for(int i = 1; i <= N; i++)
            if(!low[i])
                DFS(i, 0);

        for(int i = 1; i <= N; i++) f[i] = i;
        for(int i = 1; i <= N; i++) uniteDFS(i);

        for(int i = 1; i <= N; i++) node[i] = F(i);
    }
}

namespace TreeGraph
{
    vector<int> edg[100005];
    int E, eul[100005], h[100005], f[100005], lg2[200005], up[2][100005], upedge[100005], rmq[19][200005];
    char r[100005];
    bool vis[100005];

    void addEdge(int id)
    {
        int x = node[ edge[id].first ], y = node[ edge[id].second ];
        edge[id].first = x, edge[id].second = y;
        edg[x].push_back(id);
        edg[y].push_back(id);
    }

    void DFS(int nod, int fth)
    {
        vis[nod] = 1;
        f[nod] = fth;
        h[nod] = h[fth] + 1;
        rmq[0][++E] = nod;
        eul[nod] = E;
        up[0][nod] = up[1][nod] = nod;
        for(auto e: edg[nod])
        {
            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(nxt == fth)  continue;

            upedge[nxt] = e;
            DFS(nxt, nod);
            rmq[0][++E] = nod;
        }
    }

    int minh(int a, int b)
    {
        if(h[a] < h[b]) return a;
        return b;
    }

    int LCA(int a, int b)
    {
        int pa = eul[a], pb = eul[b];
        if(pa > pb) swap(pa, pb);
        int pw = lg2[pb - pa + 1];
        return minh(rmq[pw][pa], rmq[pw][pb - (1 << pw) + 1]);
    }

    void pre()
    {
        for(int i = 1; i <= N; i++)
            if(node[i] == i && !vis[i])
                DFS(i, 0);

        for(int i = 2; i <= E; i++)
        {
            lg2[i] = lg2[i - 1];
            if( (2 << lg2[i]) == i )    lg2[i]++;
        }
        for(int i = 1; (1 << i) <= E; i++)
            for(int j = 1; j + (1 << i) - 1 <= E; j++)
                rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }

    int UP(int dir, int x)
    {
        if(up[dir][x] == x) return x;
        return up[dir][x] = UP(dir, up[dir][x]);
    }

    void go(int x, int y, int dir)
    {
        if(h[x] <= h[y])  return;
        if(UP(dir, x) == x)
        {
            up[dir][x] = UP(dir, f[x]);
            pii e = (dir == 0 ? make_pair(x, f[x]) : make_pair(f[x], x));
            r[ upedge[x] ] = (e == edge[ upedge[x] ] ? 'R' : 'L');
        }
        go(UP(dir, x), y, dir);
    }

    void go(int x, int y)
    {
        int lca = LCA(x, y);
        go(x, lca, 0);
        go(y, lca, 1);
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[i] = {x, y};
        BiconnexGraph::addEdge(i);
    }

    BiconnexGraph::compressGraph();

    for(int i = 1; i <= M; i++)
        if(BiconnexGraph::crit[i])
        {
            int x = node[ edge[i].first ];
            int y = node[ edge[i].second ];
            TreeGraph::addEdge(i);
        }
    TreeGraph::pre();

    scanf("%d", &K);
    for(int i = 1; i <= K; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(node[x] == node[y])    continue;

        x = node[x]; y = node[y];
        TreeGraph::go(x, y);
    }

    for(int i = 1; i <= M; i++)
    {
        if(!BiconnexGraph::crit[i]) r[i] = 'B';
        else if(TreeGraph::r[i]) r[i] = TreeGraph::r[i];
        else r[i] = 'B';
    }
    printf("%s\n", r + 1);

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:203:17: warning: unused variable 'x' [-Wunused-variable]
             int x = node[ edge[i].first ];
                 ^
oneway.cpp:204:17: warning: unused variable 'y' [-Wunused-variable]
             int y = node[ edge[i].second ];
                 ^
oneway.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:209:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &K);
     ~~~~~^~~~~~~~~~
oneway.cpp:213:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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