oj.uz

Submission #432170

# Submission time Handle Problem Language Result Execution time Memory
432170 2021-06-17T23:38:22 Z ScarletS One-Way Streets (CEOI17_oneway) C++17
100 / 100
 477 ms 71184 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+1, L = 19;
int n, tin[N*4], tout[N*4], low[N], t, up[20][N*4], dp[N*4][2];
vector<array<int,2>> e[N];
vector<int> bctE[N*4];
bitset<N*4> d1, d2, d3, d4;
set<int> s[N];
map<int,int> eN[N];
string ans = "B";

void dfs(int c, int p, int k)
{
    d1[c]=1;
    tin[c]=low[c]=++t;
    for (auto i : e[c])
        if (i[1]!=p)
        {
            if (d1[i[0]])
                low[c]=min(low[c],tin[i[0]]);
            else
            {
                dfs(i[0],i[1],k);
                low[c]=min(low[c],low[i[0]]);
                if (tin[c]<low[i[0]])
                {
                    s[c].insert(i[0]);
                    s[i[0]].insert(c);
                }
            }
        }
}

void build(int c, int g)
{
    d2[c]=1;
    bctE[c].push_back(g);
    bctE[g].push_back(c);
    for (auto i : e[c])
        if (!d2[i[0]])
        {
            if (s[c].count(i[0]))
            {
                bctE[c].push_back(i[0]);
                bctE[i[0]].push_back(c);
                build(i[0],++t);
            }
            else
                build(i[0],g);
        }
}

void bctDfs(int c, int p)
{
    d3[c]=1;
    up[0][c]=p;
    for (int i=1;i<L;++i)
        up[i][c]=up[i-1][up[i-1][c]];
    tin[c]=++t;
    for (int i : bctE[c])
        if (i!=p)
            bctDfs(i,c);
    tout[c]=++t;
}

bool isAncestor(int x, int y)
{
    if (tin[x]<=tin[y]&&tout[y]<=tout[x])
        return 1;
    return 0;
}

int lca(int x, int y)
{
    if (isAncestor(x,y))
        return x;
    if (isAncestor(y,x))
        return y;
    for (int i=L-1;i>=0;--i)
        if (!isAncestor(up[i][x],y))
            x=up[i][x];
    return up[0][x];
}

void ansDfs(int c, int p)
{
    d4[c]=1;
    for (int i : bctE[c])
        if (i!=p)
        {
            ansDfs(i,c);
            dp[c][0]+=dp[i][0];
            dp[c][1]+=dp[i][1];
        }
    if (c<=n&&p<=n)
    {
        if (dp[c][0])
        {
            if (eN[c][p])
                ans[eN[c][p]]='R';
            else
                ans[eN[p][c]]='L';
        }
        else if (dp[c][1])
        {
            if (eN[c][p])
                ans[eN[c][p]]='L';
            else
                ans[eN[p][c]]='R';
        }
    }
}
  
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m,q,x,y,z;
    cin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        ans+='B';
        cin>>x>>y;
        eN[x][y]=i;
        e[x].push_back({y,i});
        e[y].push_back({x,i});
    }
    for (int i=1;i<=n;++i)
        if (!d1[i])
            dfs(i,-1,i);
    t=n;
    for (int i=1;i<=n;++i)
        if (!d2[i])
            build(i,++t);
    t=0;
    for (int i=1;i<=n;++i)
        if (!d3[i])
            bctDfs(i,0);
    tout[0]=++t;
    cin>>q;
    while (q--)
    {
        cin>>x>>y;
        z=lca(x,y);
        ++dp[x][0];
        ++dp[y][1];
        --dp[z][0];
        --dp[z][1];
    }
    for (int i=1;i<=n;++i)
        if (!d4[i])
            ansDfs(i,0);
    for (int i=1;i<=m;++i)
        cout<<ans[i];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21604 KB Output is correct
2 Correct 15 ms 21628 KB Output is correct
3 Correct 15 ms 21740 KB Output is correct
4 Correct 16 ms 21964 KB Output is correct
5 Correct 18 ms 22092 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct
7 Correct 16 ms 22092 KB Output is correct
8 Correct 16 ms 21968 KB Output is correct
9 Correct 15 ms 21708 KB Output is correct
10 Correct 15 ms 21788 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21604 KB Output is correct
2 Correct 15 ms 21628 KB Output is correct
3 Correct 15 ms 21740 KB Output is correct
4 Correct 16 ms 21964 KB Output is correct
5 Correct 18 ms 22092 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct
7 Correct 16 ms 22092 KB Output is correct
8 Correct 16 ms 21968 KB Output is correct
9 Correct 15 ms 21708 KB Output is correct
10 Correct 15 ms 21788 KB Output is correct
11 Correct 109 ms 32664 KB Output is correct
12 Correct 145 ms 35184 KB Output is correct
13 Correct 188 ms 39492 KB Output is correct
14 Correct 211 ms 47820 KB Output is correct
15 Correct 247 ms 51056 KB Output is correct
16 Correct 271 ms 63712 KB Output is correct
17 Correct 291 ms 66424 KB Output is correct
18 Correct 304 ms 63720 KB Output is correct
19 Correct 273 ms 67820 KB Output is correct
20 Correct 150 ms 37184 KB Output is correct
21 Correct 126 ms 37020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21604 KB Output is correct
2 Correct 15 ms 21628 KB Output is correct
3 Correct 15 ms 21740 KB Output is correct
4 Correct 16 ms 21964 KB Output is correct
5 Correct 18 ms 22092 KB Output is correct
6 Correct 16 ms 21708 KB Output is correct
7 Correct 16 ms 22092 KB Output is correct
8 Correct 16 ms 21968 KB Output is correct
9 Correct 15 ms 21708 KB Output is correct
10 Correct 15 ms 21788 KB Output is correct
11 Correct 109 ms 32664 KB Output is correct
12 Correct 145 ms 35184 KB Output is correct
13 Correct 188 ms 39492 KB Output is correct
14 Correct 211 ms 47820 KB Output is correct
15 Correct 247 ms 51056 KB Output is correct
16 Correct 271 ms 63712 KB Output is correct
17 Correct 291 ms 66424 KB Output is correct
18 Correct 304 ms 63720 KB Output is correct
19 Correct 273 ms 67820 KB Output is correct
20 Correct 150 ms 37184 KB Output is correct
21 Correct 126 ms 37020 KB Output is correct
22 Correct 379 ms 67776 KB Output is correct
23 Correct 450 ms 65780 KB Output is correct
24 Correct 447 ms 65956 KB Output is correct
25 Correct 401 ms 71184 KB Output is correct
26 Correct 477 ms 67264 KB Output is correct
27 Correct 446 ms 65788 KB Output is correct
28 Correct 81 ms 24388 KB Output is correct
29 Correct 247 ms 36784 KB Output is correct
30 Correct 201 ms 37060 KB Output is correct
31 Correct 286 ms 37364 KB Output is correct
32 Correct 273 ms 47460 KB Output is correct