Submission #1236738

#TimeUsernameProblemLanguageResultExecution timeMemory
1236738chikien2009One-Way Streets (CEOI17_oneway)C++20
0 / 100
2 ms2624 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, p, a, b;
int depth[100000], min_depth[100000], f[100000];
pair<int, int> e[100000];
vector<pair<int, int>> g[100000];
string s;

inline void DFS(int node, int last)
{
    for (auto &i : g[node])
    {
        if (i.second != last)
        {
            if (depth[i.first] == -1)
            {
                depth[i.first] = min_depth[i.first] = depth[node] + 1;
                DFS(i.first, i.second);
                f[node] += f[i.first];
                if (min_depth[i.first] > depth[node] && f[i.first] != 0)
                {
                    if (node == e[i.second].first)
                    {
                        s[i.second] = (f[i.first] > 0 ? 'L' : 'R');
                    }
                    else
                    {
                        s[i.second] = (f[i.first] < 0 ? 'L' : 'R');
                    }
                }
            }
            min_depth[node] = min(min_depth[node], min_depth[i.first]);
        }
    }
}

int main()
{
    setup();

    cin >> n >> m;
    fill_n(depth, n, -1);
    s.resize(m, 'B');
    for (int i = 0; i < m; ++i)
    {
        cin >> e[i].first >> e[i].second;
        e[i].first--;
        e[i].second--;
        g[e[i].first].push_back({e[i].second, i});
        g[e[i].second].push_back({e[i].first, i});
    }
    cin >> p;
    while (p--)
    {
        cin >> a >> b;
        f[a - 1]++;
        f[b - 1]--;
    }
    depth[0] = min_depth[0] = 0;
    DFS(0, -1);
    cout << s;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...