Submission #1236681

#TimeUsernameProblemLanguageResultExecution timeMemory
1236681chikien2009One-Way Streets (CEOI17_oneway)C++20
0 / 100
2 ms4928 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 head[100000], tail[100000], id[100000];
pair<int, int> e[100000];
vector<pair<int, int>> g[100000], q[100000];
string s;

inline map<int, int> DFS(int node, int par)
{
    map<int, int> cur, temp;
    for (auto & i : q[node])
    {
        cur[i.first] = i.second;
    }
    head[node] = tail[node] = a++;
    for (auto &i : g[node])
    {
        if (i.first != par)
        {
            if (head[i.first] == 0)
            {
                temp = DFS(i.first, node);
                if (temp.size() > cur.size())
                {
                    swap(temp, cur);
                }
                for (auto & j : temp)
                {
                    cur[j.first] += j.second;
                    if (cur[j.first] == 0)
                    {
                        cur.erase(j.first);
                    }
                }
                if (tail[i.first] > head[node] && !temp.empty())
                {
                    if (node == e[i.second].first)
                    {
                        s[i.second] = ((*temp.begin()).second == 1 ? 'L' : 'R');
                    }   
                    else
                    {
                        s[i.second] = ((*temp.begin()).second == -1 ? 'L' : 'R');
                    } 
                }
            }
            tail[node] = min(tail[node], tail[i.first]);
        }
    }
    return cur;
}

int main()
{
    setup();

    cin >> n >> m;
    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;
    for (int i = 0; i < p; ++i)
    {
        cin >> a >> b;
        q[a - 1].push_back({i, 1});
        q[b - 1].push_back({i, -1});
    }
    DFS(0, 0);
    cout << s;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...