Submission #160584

#	Time	Username	Problem	Language	Result	Execution time	Memory
160584		Akashi	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	350 ms	43124 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int lim = 100005;

struct edge{
    int x, y;
};
edge a[lim];

int n, m, NR;
int low[lim], id[lim], h[lim], T1[lim], T2[lim];
int TT[22][lim];

char ans[lim];
bool viz[lim];

stack <int> st;
vector <pair <int, int> > v[lim];
vector <pair <int, int> > vc[lim];
vector <int> ctc[lim];

map <pair <int, int>, int> f;

void tarjan(int nod = 1, int papa = 0){
    viz[nod] = 1;
    st.push(nod);

    bool ok = 0;
    for(auto it : v[nod]){
        if(it.first == papa){
            if(!ok) ok = 1;
            else{
                low[nod] = min(low[nod], low[it.first]);
                continue ;
            }
        }
        else{
            if(viz[it.first]) low[nod] = min(low[nod], low[it.first]);
            else{
                low[it.first] = h[it.first] = h[nod] + 1;
                tarjan(it.first, nod);
                low[nod] = min(low[nod], low[it.first]);
            }
        }
    }

    if(low[nod] == h[nod]){
        int Last = 0; ++NR;
        while(Last != nod){
            Last = st.top();
            st.pop();

            ctc[NR].push_back(Last);
            id[Last] = NR;
        }
    }
}

void dfs(int nod = 1, int papa = 0){
    viz[nod] = 1;

    for(auto it : vc[nod]){
        if(papa == it.first) continue ;
        h[it.first] = h[nod] + 1;
        TT[0][it.first] = nod;
        dfs(it.first, nod);
    }
}

inline int lca(int x, int y){
    if(x == y) return h[x];

    if(h[x] < h[y]) swap(x, y);

    int p = 1, k = 0, dif = h[x] - h[y];

    while(dif > 0){
        if(dif & p){
            dif = dif ^ p;
            x = TT[k][x];
        }
        ++k; p = p << 1;
    }

    if(x == y) return h[x];

    for(int k = 20; k >= 0 ; --k)
        if(TT[k][x] != TT[k][y]) x = TT[k][x], y = TT[k][y];

    return h[x] - 1;
}

bool dir(int i, int x, int y){
    if(id[a[i].x] == x) return 1;
    return 0;
}

void solve(int nod = 1){
    viz[nod] = 1;

    for(auto it : vc[nod]){
        if(viz[it.first]) continue ;

        solve(it.first);
        T1[nod] = min(T1[nod], T1[it.first]);
        T2[nod] = min(T2[nod], T2[it.first]);

        if(ans[it.second] != NULL) continue ;

        if(T1[it.first] <= h[nod] && T2[it.first] <= h[nod]) ans[it.second] = 'B';
        else if(T1[it.first] <= h[nod]){
            if(dir(it.second, nod, it.first)) ans[it.second] = 'L';
            else ans[it.second] = 'R';
        }
        else if(T2[it.first] <= h[nod]){
            if(dir(it.second, nod, it.first)) ans[it.second] = 'R';
            else ans[it.second] = 'L';
        }
        else ans[it.second] = 'B';


    }
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &m);

    int x, y;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        a[i].x = x; a[i].y = y;
        if(x == y){
            ans[i] = 'B';
            continue ;
        }

        if(f[{x, y}] > 0){
            ans[f[{x, y}]] = 'B';
            ans[i] = 'B';
            continue ;
        }

        v[x].push_back({y, i});
        v[y].push_back({x, i});
    }

    for(int i = 1; i <= n ; ++i) if(!viz[i]) tarjan(i);

    for(int i = 1; i <= NR ; ++i){
        for(auto it : ctc[i]){
            for(auto it2 : v[it]){
                if(id[it2.first] == i){
                    ans[it2.second] = 'B';
                    continue ;
                }
                vc[i].push_back({id[it2.first], it2.second});
            }
        }
    }

    memset(h, 0, sizeof(h));
    memset(viz, 0, sizeof(viz));
    for(int i = 1; i <= NR ; ++i){
        if(!viz[i]) dfs(i);
        T1[i] = h[i]; T2[i] = h[i];
    }

    for(int k = 1; k <= 20 ; ++k)
        for(int i = 1; i <= n ; ++i)
            TT[k][i] = TT[k - 1][TT[k - 1][i]];

    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &x, &y);
        if(id[x] == id[y]) continue ;
        x = id[x]; y = id[y];

        int wh = lca(x, y);
        T1[x] = min(T1[x], wh);
        T2[y] = min(T2[y], wh);
    }

    memset(viz, 0, sizeof(viz));
    for(int i = 1; i <= NR ; ++i) if(!viz[i]) solve(i);

    printf("%s", ans + 1);

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void solve(int)':
oneway.cpp:109:30: warning: NULL used in arithmetic [-Wpointer-arith]
         if(ans[it.second] != NULL) continue ;
                              ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
oneway.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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