제출 #1195029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195029		Hamed_Ghaffari	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	96 ms	28352 KiB

oneway

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5, LOG = 17;

int n, m, p, U[MXN], V[MXN], h[MXN], mn[MXN], dsu[MXN];
vector<int> g[MXN];

int find(int v) { return v==dsu[v] ? v : dsu[v]=find(dsu[v]); }

vector<int> bridges;

void dfs1(int v, int pid=-1) {
    if(pid!=-1) mn[v] = h[v] = h[v^U[pid]^V[pid]]+1;
    else mn[v] = h[v] = 1;
    for(int i : g[v]) {
        int u = v^U[i]^V[i];
        if(!h[u]) {
            dfs1(u, i);
            mn[v] = min(mn[v], mn[u]);
        }
        else if(i!=pid) mn[v] = min(mn[v], h[u]);
    }
    if(mn[v]==h[v]) {
        dsu[v] = v;
        if(pid!=-1) bridges.push_back(pid);
    }
    else dsu[v] = v^U[pid]^V[pid];
}

vector<pii> G[MXN];

inline void build() {
    for(int v=1; v<=n; v++)
        if(!h[v])
            dfs1(v);
    for(int i : bridges)
        G[find(U[i])].push_back({find(V[i]), i}),
        G[find(V[i])].push_back({find(U[i]), i});
}

bool vis[MXN];
int par[MXN][LOG];

void dfs2(int v) {
    h[v] = h[par[v][0]]+1;
    for(int i=1; i<LOG; i++)
        par[v][i] = par[par[v][i-1]][i-1];
    for(auto [u, i] : G[v]) 
        if(u!=par[v][0]) {
            par[u][0] = v;
            dfs2(u);
        }
}

inline int jump(int v, int d) {
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            v = par[v][i];
    return v;
}

inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[u][i]!=par[v][i])
            u = par[u][i], v = par[v][i];
    return par[u][0];
}

int up[MXN], down[MXN];
string ans;

inline void add(int u, int v) {
    if((u=find(u))==(v=find(v))) return;
    int lca = LCA(u, v);
    up[u]++;
    up[lca]--;
    down[v]++;
    down[lca]--;
}

void dfs3(int v, int pid=-1) {
    vis[v] = 1;
    for(auto [u, i] : G[v])
        if(i!=pid)
            dfs3(u, i),
            up[v] += up[u],
            down[v] += down[u];
    if(up[v])
        ans[pid] = find(U[pid])==v ? 'R' : 'L';
    else if(down[v])
        ans[pid] = find(U[pid])==v ? 'L' : 'R';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> U[i] >> V[i];
        g[U[i]].push_back(i);
        g[V[i]].push_back(i);
    }
    build();
    fill(h+1, h+n+1, 0);
    for(int v=1; v<=n; v++)
        if(!h[find(v)])
            dfs2(find(v));
    cin >> p;
    for(int i=0,u,v; i<p; i++) {
        cin >> u >> v;
        add(u, v);
    }
    ans = string(m, 'B');
    for(int v=1; v<=n; v++)
        if(!vis[find(v)])
            dfs3(find(v));
    cout << ans << '\n';
    return 0;
}

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