Submission #571195

#	Time	Username	Problem	Language	Result	Execution time	Memory
571195		Doanxem99	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	49 ms	98380 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define ar array< int , 2>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int MAX = 1e6 + 1000, LOG = 20;
int n, x[MAX], y[MAX], high[MAX], f[LOG + 1][MAX], q, c[MAX], cnt, Count, num[MAX], low[MAX], m, a, b, z;
vector < int > A[MAX], B[MAX], C;
stack< int > st;
bool d[MAX], t[MAX];
map< int, string > dd[MAX];
struct DSU
{
    vector < int > ff;
    void Init(int n) { ff.resize(n + 100, -1);}
    int Root(int x) {return (ff[x] <= -1 ? x : ff[x] = Root(ff[x]));}
    bool Join(int x, int y)
    {
        int xx = Root(x);
        int yy = Root(y);
        if (xx == yy) return false;
        //if (f[xx] > f[yy]) swap(xx, yy);
        ff[xx] += ff[yy];
        ff[yy] = xx;
        return true;
    }
    bool Check(int x, int y) {return Root(x) == Root(y);}
};
DSU dsu1;
DSU dsu2;

void DFS(int x, int p)
{
    for (int k = 1; k <= LOG; k++)
    {
        f[k][x] = f[k - 1][f[k - 1][x]];
    }
    for (int y : B[x])
    {
        if (p != y)
        {
            f[0][y] = x;
            high[y] = high[x] + 1;
            DFS(y, x);
        }
    }
}
void Prepare(int x)
{
    high[0] = -1;
    high[x] = 0;
    DFS(x, 0);
}
int LCA(int x, int y)
{
    if (high[x] < high[y]) return LCA(y, x);
    for (int k = LOG; k >= 0; k--)
    {
        if (high[f[k][x]] >= high[y])
            x = f[k][x];
    }
    for (int k = LOG; k >= 0; k--)
    {
        if (f[k][x] != f[k][y])
        {
            x = f[k][x];
            y = f[k][y];
        }
    }
    while (x != y)
    {
        x = f[0][x];
        y = f[0][y];
    }
    return x;
}
void Visit(int x, int p)
{
    num[x] = low[x] = ++Count;
    //st.push(x);
    int numChild = 0;
    for (int y : A[x])
    {
        if (y != p)
        {
            if (num[y])
            {
                low[x] = min(low[x], num[y]);
            }
            else
            {
                Visit(y, x);
                numChild++;
                low[x] = min(low[x], low[y]);
                if (low[y] >= num[y])
                {
                    B[y].push_back(x);
                    B[x].push_back(y);
                    dsu1.Join(x, y);
                    t[x] = true;
                    t[y] = true;
                }

                if (x == p) {
                    if (numChild >= 2)
                        c[x] = true;
                } else {
                    if (low[y] >= num[x])
                        c[x] = true;
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    memset(high, 0x3f, sizeof high);
    dsu1.Init(n);
    dsu2.Init(n);
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i];
        A[x[i]].push_back(y[i]);
        A[y[i]].push_back(x[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!num[i]) Visit(i, i);
    }

    int root = -1;
    for (int i = 1; i <= n; i++)
    {
        if (c[i] == 1 && !d[dsu1.Root(i)])
        {
            d[dsu1.Root(i)] = 1;
            C.push_back(i);
            root = i;
        }
    }
    for (int i = 0; i < C.size(); i++)
        for (int j = i + 1; j < C.size(); j++)
    {
        if (dsu1.Join(C[i], C[j]))
        {
            B[C[i]].push_back(C[j]);
            B[C[j]].push_back(C[i]);
            dd[C[i]][C[j]] = "B";
            dd[C[i]][C[j]] = "B";
        }
    }
    Prepare(root);
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> a >> b;
        if (t[a] == 0 || t[b] == 0) continue;
        z = LCA(a, b);
        z = dsu2.Root(z);
        while (true)
        {
            a = dsu2.Root(a);
            //cout << a << " " << z << endl;
            if (a == z) break;
            for (int i : B[a])
            {
                if (high[i] < high[a])
                {
                    dsu2.Join(i, a);
                    if (dd[a][i] == "") {
                    dd[a][i] = "R";
                    dd[i][a] = "L";
                    }
                    a = i;
                    break;
                }
            }
        }
        while (true)
        {
            b = dsu2.Root(b);
            //cout << b << " " << z << endl;
            if (b == z) break;
            for (int i : B[b])
            {
                if (high[i] < high[b])
                {
                    dsu2.Join(i, b);
                    if (dd[b][i] == "") {
                    dd[b][i] = "L";
                    dd[i][b] = "R";
                    }
                    b = i;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (t[x[i]] == 0 || t[y[i]] == 0 || dd[x[i]][y[i]] == "") cout << "B";
        else cout << dd[x[i]][y[i]];
    }
}
/*
8 11
1 2
1 2
4 3
2 3
1 3
5 1
5 2
5 6
4 5
7 3
8 7
1
6 8
*/

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < C.size(); i++)
      |                     ~~^~~~~~~~~~
oneway.cpp:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int j = i + 1; j < C.size(); j++)
      |                             ~~^~~~~~~~~~

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