Submission #1236707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236707		chikien2009	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	4928 KiB

oneway

#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];
pair<int, int> e[100000];
vector<pair<int, int>> g[100000], q[100000];
string s;

inline map<int, int> DFS(int node, int last)
{
    map<int, int> cur, temp;
    for (auto &i : q[node])
    {
        cur[i.first] += i.second;
        if (cur[i.first] == 0)
        {
            cur.erase(i.first);
        }
    }
    head[node] = tail[node] = a++;
    for (auto &i : g[node])
    {
        if (i.second != last)
        {
            if (head[i.first] == -1)
            {
                temp = DFS(i.first, i.second);
                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');
                    }
                }
                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);
                    }
                }
            }
            tail[node] = min(tail[node], tail[i.first]);
        }
    }
    return cur;
}

int main()
{
    setup();

    cin >> n >> m;
    fill_n(head, 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;
    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, -1);
    cout << s;
    return 0;
}

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