oj.uz

Submission #117570

# Submission time Handle Problem Language Result Execution time Memory
117570 2019-06-16T15:29:54 Z johutha One-Way Streets (CEOI17_oneway) C++14
100 / 100
 499 ms 38216 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 77 ms 12912 KB Output is correct
12 Correct 96 ms 16156 KB Output is correct
13 Correct 128 ms 21856 KB Output is correct
14 Correct 154 ms 29920 KB Output is correct
15 Correct 187 ms 31868 KB Output is correct
16 Correct 163 ms 31712 KB Output is correct
17 Correct 151 ms 33476 KB Output is correct
18 Correct 169 ms 31696 KB Output is correct
19 Correct 146 ms 34784 KB Output is correct
20 Correct 102 ms 20244 KB Output is correct
21 Correct 89 ms 19796 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 77 ms 12912 KB Output is correct
12 Correct 96 ms 16156 KB Output is correct
13 Correct 128 ms 21856 KB Output is correct
14 Correct 154 ms 29920 KB Output is correct
15 Correct 187 ms 31868 KB Output is correct
16 Correct 163 ms 31712 KB Output is correct
17 Correct 151 ms 33476 KB Output is correct
18 Correct 169 ms 31696 KB Output is correct
19 Correct 146 ms 34784 KB Output is correct
20 Correct 102 ms 20244 KB Output is correct
21 Correct 89 ms 19796 KB Output is correct
22 Correct 387 ms 34652 KB Output is correct
23 Correct 412 ms 32740 KB Output is correct
24 Correct 479 ms 32864 KB Output is correct
25 Correct 408 ms 38216 KB Output is correct
26 Correct 499 ms 34156 KB Output is correct
27 Correct 479 ms 32868 KB Output is correct
28 Correct 52 ms 6864 KB Output is correct
29 Correct 326 ms 20948 KB Output is correct
30 Correct 305 ms 21076 KB Output is correct
31 Correct 282 ms 21512 KB Output is correct
32 Correct 311 ms 26360 KB Output is correct