Submission #563703

#	Time	Username	Problem	Language	Result	Execution time	Memory
563703		minhcool	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	19 ms	42580 KiB

oneway

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

#define int long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, p;

vector<int> Adj[N], Adj2[N];
vector<ii> Adj3[N];

vector<ii> edges;
set<ii> bridges;

int cnt;
int ti[N], low[N];

char ans[N];

void dfs(int u, int p){
    cnt++;
    ti[u] = low[u] = cnt;
    for(auto v : Adj[u]){
        if(ti[v]){
            if(v != p) low[u] = min(low[u], ti[v]);
        }
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(ti[u] < low[v]){
                bridges.insert({min(u, v), max(u, v)});
            }
        }
    }
}

int cnt_comp;
int comp[N];

void dfs2(int u){
    //cout << u << "\n";
    comp[u] = cnt_comp;
    for(auto v : Adj2[u]){
        if(comp[v]) continue;
        dfs2(v);
    }
}

int sz[N], rt[N], answ[N];

vector<ii> que[N];
set<ii> ques[N];// for component

int sparse[N][20], d[N];
int ind[N];

void dfs3(int u, int p){
    for(auto it : Adj3[u]){
        int v = it.fi;
        if(v == p) continue;
        d[v] = d[u] + 1;
        sparse[v][0] = u;
        for(int i = 1; i <= 19; i++) sparse[v][i] = sparse[sparse[v][i - 1]][i - 1];
        //cout << v << "\n";
        //for(int i = 0; i <= 19; i++) cout << sparse[v][i] << " ";
        //cout << "\n";
        ind[v] = it.se;
        dfs3(v, u);
    }
}

int lca(int x, int y){
    if(d[x] > d[y]) swap(x, y);
    //cout << x << " " << y << " " << d[x] << " " << d[y] << "\n";
    for(int i = 19; i >= 0; i--){
        if(d[y] >= (d[x] + (1LL << i))){
            cout << i << "\n";
            y = sparse[y][i];
        }
    }
    //cout << x << " " << y << "\n";
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(sparse[x][i] != sparse[y][i]){
            x = sparse[x][i];
            y = sparse[y][i];
        }
    }
    return sparse[x][0];
}

int root(int x){
    return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

void merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y], rt[y] = x;
    for(auto it : ques[y]) ques[x].insert(it);
    ques[y].clear();
}

map<ii, vector<int>> mp;

void dfs4(int u, int p){
    for(auto it : Adj3[u]){
        int v = it.fi;
        if(v == p) continue;
        dfs4(v, u);
        merge(u, v);
    }
    //return;
    int temp = root(u);
    for(auto it : que[u]) ques[temp].insert(it);
    while(ques[temp].size() && (*ques[temp].begin()).fi >= d[u]) ques[temp].erase(ques[temp].begin());
    if(ques[temp].size()){
        bool x = (*ques[temp].begin()).se;
        answ[ind[u]] = (!x ? u : p);
    }
    else ans[ind[u]] = 'B';
}

void process(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        edges.pb({min(x, y), max(x, y)});
        mp[{min(x, y), max(x, y)}].pb(i);
        //Adj[x].pb(y);
        //Adj[y].pb(x);
    }
    for(auto it : mp){
        Adj[it.fi.fi].pb(it.fi.se);
        Adj[it.fi.se].pb(it.fi.fi);
    }
    for(int i = 1; i <= n; i++) if(!ti[i]) dfs(i, i);
    //for(auto it : bridges) cout << it.fi << " " << it.se << "\n";
    for(int i = 0; i < m; i++){
        if(mp[edges[i]].size() > 1){
            ans[i] = 'B';
            continue;
        }
        if(bridges.find(edges[i]) == bridges.end()){
            ans[i] = 'B';
            Adj2[edges[i].fi].pb(edges[i].se);
            Adj2[edges[i].se].pb(edges[i].fi);
           // cout << edges[i].fi << " " << edges[i].se << "\n";
            continue;
        }
        //cout << i << "\n";
    }
    for(int i = 1; i <= n; i++){
        if(!comp[i]){
            cnt_comp++;
            dfs2(i);
        }
    }
   // return;
    for(int i = 0; i < m; i++){
        if(ans[i] != 'B'){
            assert(comp[edges[i].fi] != comp[edges[i].se]);
            //cout << edges[i].fi << " " << edges[i].se << "\n";
            //cout << comp[edges[i].fi] << " " << comp[edges[i].se] << "\n";
            Adj3[comp[edges[i].fi]].pb({comp[edges[i].se], i});
            Adj3[comp[edges[i].se]].pb({comp[edges[i].fi], i});
        }
    }
    //return;
    for(int i = 1; i <= cnt_comp; i++) if(!d[i]) dfs3(i, i);
    cin >> p;
    for(int i = 1; i <= p; i++){
        int x, y;
        cin >> x >> y;
        if(comp[x] == comp[y]) continue;
        int z = lca(comp[x], comp[y]);
        //cout << comp[x] << " " << comp[y] << " " << z << "\n";
        que[comp[x]].pb({d[z], 0});
        que[comp[y]].pb({d[z], 1});
    }
    for(int i = 1; i <= n; i++){
        sz[i] = 1, rt[i] = i;
    }
    for(int i = 1; i <= cnt_comp; i++){
        if(!d[i]){
          //  cout << i << "\n";
            dfs4(i, i);
        }
    }
    for(int i = 0; i < m; i++){
        if(ans[i] != 'B'){
            if(answ[i] == comp[edges[i].fi]) ans[i] = 'L';
            else ans[i] = 'R';
        }
        cout << ans[i];
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    process();
}

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