제출 #683996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683996		PoonYaPat	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	152 ms	23292 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,k,disc[100001],low[100001],cnt,p[100001][18],val_up[100001],val_down[100001],level[100001];
pii edge[100001];
char ans[100001];
vector<pii> adj[100001];
bool bridge[100001],vis[100001];

void tarjan(int x, int line) {
    disc[x]=low[x]=++cnt;
    for (auto s : adj[x]) {
        if (s.second==line) continue;
        if (disc[s.first]) low[x]=min(low[x],disc[s.first]);
        else {
            tarjan(s.first,s.second);
            low[x]=min(low[x],low[s.first]);
            if (low[s.first]>disc[x]) bridge[s.second]=true;
        }
    }
}

void dfs1(int x, int par) {
    vis[x]=true;
    level[x]=level[par]+1;
    p[x][0]=par;
    for (int i=1; i<=17; ++i) p[x][i]=p[p[x][i-1]][i-1];

    for (auto s : adj[x]) {
        if (vis[s.first]) continue;
        dfs1(s.first,x);
    }
}

int lca(int x, int y) {
    if (level[y]>level[x]) swap(x,y);
    int dif=level[x]-level[y];
    for (int i=0; i<18; ++i) {
        if (dif&(1<<i)) x=p[x][i];
    }

    if (x==y) return x;

    for (int i=17; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}

void dfs2(int x) {
    vis[x]=true;
    for (auto s : adj[x]) {
        if (vis[s.first]) continue;
        dfs2(s.first);
        val_up[x]+=val_up[s.first];
        val_down[x]+=val_down[s.first];

        if (bridge[s.second]) {
            if (val_up[s.first]>0) { //s.first to x
                if (edge[s.second].first==x) ans[s.second]='L';
                else ans[s.second]='R';
            } else if (val_down[s.first]>0) { //x to s.first
                if (edge[s.second].first==x) ans[s.second]='R';
                else ans[s.second]='L';
            } else {
                ans[s.second]='B';
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b; cin>>a>>b;
        adj[a].push_back(pii(b,i));
        adj[b].push_back(pii(a,i));
        edge[i]=pii(a,b);
    }
    for (int i=1; i<=n; ++i) {
        if (!disc[i]) {
            tarjan(i,-1);
            dfs1(i,0);
        }
    }
    int q; cin>>q;
    while (q--) {
        int a,b; cin>>a>>b;
        int LCA=lca(a,b);
        ++val_up[a]; --val_up[LCA];
        ++val_down[b]; --val_down[LCA];


    }
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; ++i) {
        if (!vis[i]) dfs2(i);
    }
    for (int i=0; i<m; ++i) {
        if (!ans[i]) cout<<'B';
        else cout<<ans[i];
    }

}

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