oj.uz

Submission #432169

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

const int N = 2e5+1, L = 20;
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 28 ms 42692 KB Output is correct
2 Correct 27 ms 42748 KB Output is correct
3 Correct 28 ms 42956 KB Output is correct
4 Correct 28 ms 43096 KB Output is correct
5 Correct 29 ms 43144 KB Output is correct
6 Correct 28 ms 42844 KB Output is correct
7 Correct 28 ms 43136 KB Output is correct
8 Correct 27 ms 43112 KB Output is correct
9 Correct 27 ms 42956 KB Output is correct
10 Correct 28 ms 42960 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 42692 KB Output is correct
2 Correct 27 ms 42748 KB Output is correct
3 Correct 28 ms 42956 KB Output is correct
4 Correct 28 ms 43096 KB Output is correct
5 Correct 29 ms 43144 KB Output is correct
6 Correct 28 ms 42844 KB Output is correct
7 Correct 28 ms 43136 KB Output is correct
8 Correct 27 ms 43112 KB Output is correct
9 Correct 27 ms 42956 KB Output is correct
10 Correct 28 ms 42960 KB Output is correct
11 Correct 125 ms 54956 KB Output is correct
12 Correct 124 ms 57556 KB Output is correct
13 Correct 181 ms 61932 KB Output is correct
14 Correct 216 ms 70664 KB Output is correct
15 Correct 246 ms 73812 KB Output is correct
16 Correct 298 ms 86920 KB Output is correct
17 Correct 292 ms 89528 KB Output is correct
18 Correct 338 ms 86880 KB Output is correct
19 Correct 278 ms 90932 KB Output is correct
20 Correct 130 ms 59756 KB Output is correct
21 Correct 131 ms 59500 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 42692 KB Output is correct
2 Correct 27 ms 42748 KB Output is correct
3 Correct 28 ms 42956 KB Output is correct
4 Correct 28 ms 43096 KB Output is correct
5 Correct 29 ms 43144 KB Output is correct
6 Correct 28 ms 42844 KB Output is correct
7 Correct 28 ms 43136 KB Output is correct
8 Correct 27 ms 43112 KB Output is correct
9 Correct 27 ms 42956 KB Output is correct
10 Correct 28 ms 42960 KB Output is correct
11 Correct 125 ms 54956 KB Output is correct
12 Correct 124 ms 57556 KB Output is correct
13 Correct 181 ms 61932 KB Output is correct
14 Correct 216 ms 70664 KB Output is correct
15 Correct 246 ms 73812 KB Output is correct
16 Correct 298 ms 86920 KB Output is correct
17 Correct 292 ms 89528 KB Output is correct
18 Correct 338 ms 86880 KB Output is correct
19 Correct 278 ms 90932 KB Output is correct
20 Correct 130 ms 59756 KB Output is correct
21 Correct 131 ms 59500 KB Output is correct
22 Correct 415 ms 92044 KB Output is correct
23 Correct 448 ms 90108 KB Output is correct
24 Correct 476 ms 90240 KB Output is correct
25 Correct 399 ms 95476 KB Output is correct
26 Correct 431 ms 91556 KB Output is correct
27 Correct 486 ms 90064 KB Output is correct
28 Correct 91 ms 46660 KB Output is correct
29 Correct 238 ms 60432 KB Output is correct
30 Correct 205 ms 60668 KB Output is correct
31 Correct 279 ms 61028 KB Output is correct
32 Correct 273 ms 71236 KB Output is correct