제출 #559262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559262		fatemetmhr	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	301 ms	155328 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back

const int maxn5 = 1e6 + 10;
const int lg    = 20;

int ty[maxn5], a[maxn5], b[maxn5], h[maxn5];
int par[lg + 2][maxn5], mn[maxn5], req[maxn5][2];
int cmp[maxn5], no = 0;
bool mark[maxn5], brsh[maxn5];
pair <int, int> e[maxn5];
vector <pair<int, int>> adj[maxn5], jda[maxn5];

inline void make_dir(int id, int u, int v){
    //cout << "dir of " << id << ' ' << u << ' ' << v << endl;
    ty[id] = 1;
    if(u == cmp[e[id].fi] && v == cmp[e[id].se])
        ty[id] = 2;
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b])
        a = par[i][a], b = par[i][b];
    return par[0][a];
}

inline void dfs_det(int v, int p){
    mn[v] = h[v];
    mark[v] = true;
    for(auto [u, id] : adj[v]) if(id != p){
        if(!mark[u]){
            h[u] = h[v] + 1;
            dfs_det(u, id);
            mn[v] = min(mn[v], mn[u]);
            if(mn[u] > h[v])
                brsh[id] = true;
            //cout << "det " << v << ' ' << u  << ' ' << id << ' ' << mn[u] << ' ' << brsh[id] << endl;
        }
        else
            mn[v] = min(mn[v], mn[u]);
    }
    return;
}

inline void dfs_bor(int v){
    mark[v] = true;
    cmp[v] = no;
    //cout << "seeing " << v << ' ' << no << endl;
    for(auto [u, id] : adj[v]) if(!mark[u] && !brsh[id]){
        dfs_bor(u);
    }
}

inline void dfs_lca(int v){
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    for(auto [u, id] : jda[v]) if(u != par[0][v]){
        par[0][u] = v;
        h[u] = h[v] + 1;
        dfs_lca(u);
    }
}

inline void dfs_dir(int v){
    for(auto [u, id] : jda[v]) if(u != par[0][v]){
        dfs_dir(u);
        if(req[u][0])
            make_dir(id, u, v);
        if(req[u][1])
            make_dir(id, v, u);
        assert(!(req[u][0] && req[u][1]));

        req[v][0] += req[u][0];
        req[v][1] += req[u][1];
    }
    return;
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, p; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
        e[i] = {a, b};
    }
    for(int i = 0; i < n; i++) if(!mark[i])
        dfs_det(i, -1);
    memset(mark, false, sizeof mark);
    for(int i = 0; i < n; i++) if(!mark[i]){
        dfs_bor(i);
        no++;
    }

    for(int i = 0; i < n; i++) for(auto [u, id] : adj[i]) if(cmp[u] != cmp[i]){
        jda[cmp[i]].pb({cmp[u], id});
        //cout << "from " << i << ' ' << u << ' '<< id << ' '<< cmp[u] << ' ' << cmp[i] << endl;
    }
    memset(par, -1, sizeof par);
    memset(h, 0, sizeof h);
    for(int i = 0; i < n; i++) if(par[0][i] == -1)
        dfs_lca(i);
    cin >> p;
    for(int i = 0; i < p; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        a = cmp[a];
        b = cmp[b];
        if(a == b)
            continue;
        int c = lca(a, b);
        assert(c != -1);
        //cout << "for " << a << ' ' << b << ' ' << c << endl;
        req[a][0]++;
        req[b][1]++;
        req[c][0]--;
        req[c][1]--;
    }

    for(int i = 0; i < n; i++) if(par[0][i] == -1)
        dfs_dir(i);

    for(int i = 0; i < m; i++){
        if(!brsh[i] || ty[i] == 0)
            cout << 'B';
        else
            cout << (ty[i] == 1 ? 'L' : 'R');
    }

    cout << endl;

}

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