Submission #321026

#	Time	Username	Problem	Language	Result	Execution time	Memory
321026		hoangtung_pro	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	258 ms	24420 KiB

oneway

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 1e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, m, k, a[N], b[N];

vector < ii > adj[N];

int cnt = 0, num[N], low[N], h[N], p[N][20], pred[N], par[N], res[N];
bool brid[N];

void dfs(int u) {
    num[u] = low[u] = ++ cnt;
    int v, i;
    for(ii x : adj[u]) {
        tie(v, i) = x;
        if(num[v]) {
            if(p[v][0] == u) brid[v] = 0;
            if(v != p[u][0]) low[u] = min(low[u], low[v]);
        }
        else {
            h[v] = h[u] + 1, p[v][0] = u, pred[v] = i;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if(low[v] > num[u]) brid[v] = 1;
        }
    }
}

int LCA(int u, int v)
{
    if(h[u] > h[v]) swap(u, v);

    for(int i=18;i>=0;--i) if( h[p[v][i]] >= h[u] ) v = p[v][i];

    if(u == v) return u;

    for(int i=18;i>=0;--i)
    {
        if( p[u][i] != p[v][i] )
        {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

int get(int x) {
    if(x == par[x]) return x;
    return par[x] = get(par[x]);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("trash.inp","r",stdin);
    // freopen("trash.out","w",stdout);

    cin >> n >> m;
    for(int i=1;i<=m;++i) {
        cin >> a[i] >> b[i];
        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    for(int i=1;i<=n;++i) if(!num[i]) dfs(i);

    for(int j=1;j<=18;++j)
    for(int i=1;i<=n;++i)  if((1<<j) <= h[i]) p[i][j] = p[p[i][j-1]][j-1];

    for(int i=1;i<=n;++i) par[i] = i;

    cin >> k;
    while(k --) {
        int u, v, pa;
        cin >> u >> v;
        pa = LCA(u, v);

        u = get(u);
        while(h[u] > h[pa]) {
            if(brid[u]) res[pred[u]] = -1;
            par[u] = p[u][0];
            u = get(u);
        }

        v = get(v);
        while(h[v] > h[pa]) {
            if(brid[v]) res[pred[v]] = 1;
            par[v] = p[v][0];
            v = get(v);
        }
    }

    for(int i=1;i<=n;++i) if(brid[i] && b[pred[i]] != i) {
        res[pred[i]] *= -1;
    }

    for(int i=1;i<=m;++i) {
        if(!res[i]) cout << "B";
        if(res[i] == 1) cout << "R";
        if(res[i] == -1) cout << "L";
    }
}

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