oj.uz

Submission #585685

# Submission time Handle Problem Language Result Execution time Memory
585685 2022-06-29T08:21:20 Z Hanksburger One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 2644 KB 
#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;
        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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -