Submission #117570

#	Time	Username	Problem	Language	Result	Execution time	Memory
117570		johutha	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	499 ms	38216 KiB

oneway

#include <vector>
#include <iostream>
#include <algorithm>

#define int int64_t

using namespace std;


struct edge
{
    int from, to, nr;
    bool bridge = false;
    char ch = 'U';

    int getend(int fr)
    {
        if (fr == from) return to;
        return from;
    }

    bool l = false;
    bool r = false;

    void print()
    {
        cout << from << " -> " << to << ", b=" << bridge << ", lr=" << l << r << "\n";
    }
};


int log2(int n)
{
    return 32 - __builtin_clz(n) - 1;
}

struct graph
{
    vector<edge> edges;
    vector<vector<int>> edgepointers;

    vector<int> paredges;

    vector<vector<int>> parents;
    vector<int> levels;

    vector<int> visited;

    int ln1;
    int n;

    int dfs(int curr, int from, int &num)
    {
        visited[curr] = num;
        num++;

        int gmin = visited[curr];

        for (int nep : edgepointers[curr])
        {
            edge e = edges[nep];
            int next = e.getend(curr);
            if (nep == from) continue;
            if (visited[next] == -1)
            {
                int nv = dfs(next, nep, num);
                if (nv > visited[curr]) edges[nep].bridge = true;
                gmin = min(gmin, nv);
            }
            gmin = min(gmin, visited[next]);
        }
        return gmin;
    }
    vector<bool> visisec;
    void structurize(int curr, int par, int pare)
    {
        if (visisec[curr]) return;
        visisec[curr] = true;
        if (par != -1) levels[curr] = levels[par] + 1;
        else levels[curr] = 0;
        paredges[curr] = pare;
        parents[0][curr] = par;
        for (int nep : edgepointers[curr])
        {
            int next = edges[nep].getend(curr);
            structurize(next, curr, nep);
        }
    }

    void buildlct(int in)
    {
        n = in;
        ln1 = log2(n) + 1;
        for (int i = 1; i < ln1; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (parents[i - 1][j] == -1) parents[i][j] = -1;
                else parents[i][j] = parents[i - 1][parents[i - 1][j]];
            }
        }
    }

    void printlct()
    {
        /*for (auto a : parents)
        {
            for (auto i : a)
            {
                cout << i << " ";
            }
            cout << "\n";
        }

        for (int i : levels)
        {
            cout << i << "\n";
        }*/
        for (int i : upwards)
        {
            cout << i << " ";
        }
        cout << "\n";
        for (int i : downwards)
        {
            cout << i << " ";
        }
        cout << "\n";
    }

    int lca(int a, int b)
    {
        if (levels[b] > levels[a]) swap(a, b);
        int ldiff = levels[a] - levels[b];

        for (int i = 0; i < ln1; i++)
        {
            if (ldiff & (1LL<<i))
            {
                a = parents[i][a];
            }
        }
        if (a == b) return a;

        for (int i = ln1 - 1; i > -1; i--)
        {
            if (parents[i][a] != parents[i][b])
            {
                a = parents[i][a];
                b = parents[i][b];
            }
        }
        if (a == b) return a;
        return parents[0][a];
    }

    vector<int> upwards;
    vector<int> downwards;

    void finalize()
    {
        vector<pair<int,int>> order;
        for (int i = 0; i < n; i++)
        {
            order.push_back({-levels[i], i});
        }
        sort(order.begin(), order.end());
        for (auto p : order)
        {
            int curr = p.second;
            if (curr == 0) continue;
            int par = parents[0][curr];
            if (downwards[curr] != -1 && levels[downwards[curr]] < levels[curr])
            {
                if (edges[paredges[curr]].bridge)
                {
                    edges[paredges[curr]].r = (curr == edges[paredges[curr]].to);
                    edges[paredges[curr]].l = (curr == edges[paredges[curr]].from);
                }
                if (downwards[par] == -1)
                {
                    downwards[par] = downwards[curr];
                }
                else if (levels[downwards[curr]] < levels[downwards[par]]) downwards[par] = downwards[curr];
            }
            if (upwards[curr] != -1 && levels[upwards[curr]] < levels[curr])
            {
                if (edges[paredges[curr]].bridge)
                {
                    edges[paredges[curr]].l = (curr == edges[paredges[curr]].to);
                    edges[paredges[curr]].r = (curr == edges[paredges[curr]].from);
                }
                if (upwards[par] == -1)
                {
                    upwards[par] = upwards[curr];
                }
                else if (levels[upwards[curr]] < levels[upwards[par]]) upwards[par] = upwards[curr];
            }
        }
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph g;
    g.edgepointers.resize(n);

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to;
        e.from--;
        e.to--;
        e.nr = i;
        g.edges.push_back(e);
        g.edgepointers[e.from].push_back(g.edges.size() - 1);
        g.edgepointers[e.to].push_back(g.edges.size() - 1);
    }

    int num = 0;
    g.visited.resize(n, -1);
    for (int i = 0; i < n; i++)
    {
        if (g.visited[i] == -1) g.dfs(i, -1, num);
    }

    for (int i = 0; i < m; i++)
    {
        if (!g.edges[i].bridge) g.edges[i].ch = 'B';
    }

    g.visisec.resize(n, false);
    g.levels.resize(n, -1);
    g.parents.resize(log2(n) + 1, vector<int>(n, -1));
    g.paredges.resize(n, -1);
    for (int i = 0; i < n; i++)
    {
        if (!g.visisec[i]) g.structurize(i, -1, -1);
    }
    g.buildlct(n);
    g.upwards.resize(n, -1);
    g.downwards.resize(n, -1);

    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        int lc = g.lca(a, b);
        if (g.upwards[a] != -1)
        {
            if (g.levels[g.upwards[a]] > g.levels[lc]) g.upwards[a] = lc;
        }
        else g.upwards[a] = lc;
        if (g.downwards[b] != -1)
        {
            if (g.levels[g.downwards[b]] > g.levels[lc]) g.downwards[b] = lc;
        }
        else g.downwards[b] = lc;
    }

    g.finalize();
    
    for (int i = 0; i < m; i++)
    {
        if (g.edges[i].ch == 'U')
        {
            if (g.edges[i].r) g.edges[i].ch = 'R';
            else if (g.edges[i].l) g.edges[i].ch = 'L';
            else g.edges[i].ch = 'B';
        }
    }

    for (int i = 0; i < m; i++)
    {
        cout << g.edges[i].ch;
    }
    cout << "\n";
}

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