oj.uz

Submission #414081

# Submission time Handle Problem Language Result Execution time Memory
414081 2021-05-30T00:38:08 Z ScarletS One-Way Streets (CEOI17_oneway) C++17
0 / 100
 12 ms 19148 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 1e5+3, K = 5, L = __lg(N*K)+2;
int n, edgeList[N][2], tin[N], low[N], t, p[N][2], cur, Tin[N], Tout[N], timer, up[L][N*K], dp[N*K];
vector<int> bct[N*K];
vector<array<int,2>> e[N];
string ans(N, 'B');
bitset<N> d1, d2, ap;
bitset<N*K> d3;
set<int> s[N];

void dfs(int c, int pt, int pi)
{
    p[c][0]=pt;
    p[c][1]=pi;
    d1[c]=1;
    tin[c]=low[c]=++t;
    vector<int> v;
    for (auto i : e[c])
        if (i[1]!=pi)
        {
            if (d1[i[0]])
                low[c]=min(low[c],tin[i[0]]);
            else
            {
                dfs(i[0],c,i[1]);
                low[c]=min(low[c],low[i[0]]);
                if (pt==0)
                    v.push_back(i[0]);
                else if (tin[c]<=low[i[0]])
                {
                    ap[c]=1;
                    s[c].insert(i[0]);
                }
            }
        }
    if (pt==0&&v.size()>1)
    {
        ap[c]=1;
        for (int i : v)
            if (tin[c]<low[i])
                s[c].insert(i);
    }
}

void buildBCT(int c, int gp)
{
    bct[c].push_back(gp);
    bct[gp].push_back(c);
    d2[c]=1;
    for (auto i : e[c])
        if (!d2[i[0]])
        {
            if (ap[c]&&s[c].count(i[0]))
            {
                ++cur;
                bct[c].push_back(cur);
                buildBCT(i[0],cur);
            }
            else
                buildBCT(i[0],gp);
        }
}

void dfsLCA(int c, int pt)
{
    // up[0][c]=pt;
    // for (int i=1;i<L;++i)
    //     up[i][c]=up[i-1][up[i-1][c]];
    Tin[c]=++timer;
    for (int i : bct[c])
        if (i!=pt)
            dfsLCA(i,c);
    Tout[c]=++timer;
}

// 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 dfsAns(int c)
{
    d3[c]=1;
    //cout<<c<<": "<<dp[c]<<"\n";
    for (int i : bct[c])
        if (!d3[i])
        {
            dfsAns(i);
            dp[c]+=dp[i];
        }
    if (c>n)
        return;
    if (dp[c]>0)
    {
        if (c==edgeList[p[c][1]][0])
            ans[p[c][1]]='R';
        else
            ans[p[c][1]]='L';
    }
    else if (dp[c]<0)
    {
        if (c==edgeList[p[c][1]][0])
            ans[p[c][1]]='L';
        else
            ans[p[c][1]]='R';
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m,x,y,q;
    cin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        cin>>x>>y;
        edgeList[i][0]=x;
        edgeList[i][1]=y;
        e[x].push_back({y,i});
        e[y].push_back({x,i});
    }
    cur=n;
    for (int i=1;i<=n;++i)
        if (!d1[i])
        {
            dfs(i,0,0);
            buildBCT(i,++cur);
            dfsLCA(i,0);
        }
    Tout[0]=++timer;
    cin>>q;
    while (q--)
    {
        cin>>x>>y;
        ++dp[x];
        --dp[y];
    }
    for (int i=1;i<=n;++i)
        if (!d3[i])
            dfsAns(i);
    for (int i=1;i<=m;++i)
        cout<<ans[i];
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -