oj.uz

Submission #585735

# Submission time Handle Problem Language Result Execution time Memory
585735 2022-06-29T09:25:41 Z Hanksburger One-Way Streets (CEOI17_oneway) C++17
100 / 100
 62 ms 15092 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;
        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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2692 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2692 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 34 ms 8912 KB Output is correct
12 Correct 39 ms 9724 KB Output is correct
13 Correct 54 ms 10788 KB Output is correct
14 Correct 52 ms 11288 KB Output is correct
15 Correct 62 ms 11276 KB Output is correct
16 Correct 43 ms 9420 KB Output is correct
17 Correct 43 ms 10960 KB Output is correct
18 Correct 42 ms 9468 KB Output is correct
19 Correct 44 ms 12112 KB Output is correct
20 Correct 38 ms 9276 KB Output is correct
21 Correct 43 ms 8960 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2692 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 34 ms 8912 KB Output is correct
12 Correct 39 ms 9724 KB Output is correct
13 Correct 54 ms 10788 KB Output is correct
14 Correct 52 ms 11288 KB Output is correct
15 Correct 62 ms 11276 KB Output is correct
16 Correct 43 ms 9420 KB Output is correct
17 Correct 43 ms 10960 KB Output is correct
18 Correct 42 ms 9468 KB Output is correct
19 Correct 44 ms 12112 KB Output is correct
20 Correct 38 ms 9276 KB Output is correct
21 Correct 43 ms 8960 KB Output is correct
22 Correct 59 ms 12144 KB Output is correct
23 Correct 58 ms 10548 KB Output is correct
24 Correct 58 ms 10596 KB Output is correct
25 Correct 58 ms 15092 KB Output is correct
26 Correct 55 ms 11664 KB Output is correct
27 Correct 55 ms 10628 KB Output is correct
28 Correct 34 ms 6868 KB Output is correct
29 Correct 60 ms 10092 KB Output is correct
30 Correct 61 ms 10132 KB Output is correct
31 Correct 53 ms 10520 KB Output is correct
32 Correct 51 ms 12340 KB Output is correct