제출 #585735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585735		Hanksburger	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	62 ms	15092 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
int x[100005], y[100005], d1[100005], d2[100005];
vector<pair<int, int> > adj[100005];
bool ok[100005], ko[100005];
char ans[100005];
void dfs1(int u, int p)
{
    ok[u]=1;
    for (pair<int, int> i:adj[u])
    {
        int v=i.first;
        if (v==p)
            continue;
        if (ok[v])
        {
            if (x[i.second]==u)
                swap(x[i.second], y[i.second]);
        }
        else
        {
            ko[i.second]=1;
            dfs1(v, u);
        }
    }
}
void dfs2(int u, int p)
{
    ok[u]=0;
    for (pair<int, int> i:adj[u])
    {
        int v=i.first;
        if (v==p || !ok[v])
            continue;
        dfs2(v, u);
        d1[u]+=d1[v];
        d2[u]+=d2[v];
        if (d1[v] || !d2[v])
            ans[i.second]='B';
        else
            ans[i.second]=((d2[v]>0)^(x[i.second]==u))?'R':'L';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, p;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        cin >> x[i] >> y[i];
        adj[x[i]].push_back({y[i], i});
        adj[y[i]].push_back({x[i], i});
    }
    for (int i=1; i<=n; i++)
        if (!ok[i])
            dfs1(i, 0);
    for (int i=1; i<=m; i++)
    {
        if (!ko[i])
        {
            ans[i]='B';
            d1[x[i]]++;
            d1[y[i]]--;
        }
    }
    cin >> p;
    for (int i=1; i<=p; i++)
    {
        int u, v;
        cin >> u >> v;
        d2[u]++;
        d2[v]--;
    }
    for (int i=1; i<=n; i++)
        if (ok[i])
            dfs2(i, 0);
    for (int i=1; i<=m; i++)
        cout << ans[i];
    return 0;
}

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