제출 #1179340

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

oneway

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
int n, m, q, num[nx], low[nx], tim=0, dem=0, id[nx], dp[nx];
ii a[nx], ed[nx];
bool vis[nx], del[nx];
stack<int> st;
vector<int> adj[nx];
vector<ii> g[nx];
char ans[nx];
void dfs(int p, int u)
{
    num[u]=low[u]=++tim;
    st.push(u);
    for(int id:adj[u])
    {
        int v=a[id].fi^a[id].se^u;
        if(id==p) continue;
        if(!num[v])
            dfs(id, v), low[u]=min(low[u], low[v]);
        else low[u]=min(low[u], num[v]);
    }
    if(low[u]>=num[u])
    {
        int v;
        dem++;
        do
        {
            v=st.top();
            st.pop();
            id[v]=dem;
            del[v]=1;
        }
        while(v!=u);
    }
}
void dfs1(int u, int sus)
{
    vis[u]=1;
    for(auto it:g[u])
    {
        int v=it.fi;
        if(!vis[v])
            dfs1(v, it.se), dp[u]+=dp[v];
    }
    if(sus)
    {
        if(!dp[u]) ans[sus]='B';
        else
        {
            if(dp[u]<0) ans[sus]=(u==id[a[sus].se])?'R':'L';
            else ans[sus]=(u==id[a[sus].fi])?'R':'L';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].emplace_back(i);
        adj[v].emplace_back(i);
        a[i]={u, v};
    }
    for(int i = 1; i <= n; i++)
        if(!num[i]) dfs(0, i);
    for(int i = 1; i <= m; i++)
    {
        int u=a[i].fi, v=a[i].se;
        if(id[u]!=id[v]) g[id[u]].emplace_back(id[v], i), g[id[v]].emplace_back(id[u], i);
        else ans[i]='B';
    }
    cin>>q;
    while(q--)
    {
        int x, y;
        cin>>x>>y;
        dp[id[x]]++, dp[id[y]]--;
    }
    for(int i = 1; i <= dem; i++)
        if(!vis[i])
            dfs1(i, 0);
    for(int i = 1; i <= m; i++)
        cout<<ans[i];
}

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