Submission #1236733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236733		chikien2009	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3 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 depth[100000], min_depth[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;
    }
    for (auto &i : g[node])
    {
        if (i.second != last)
        {
            if (depth[i.first] == -1)
            {
                depth[i.first] = min_depth[i.first] = depth[node] + 1;
                temp = DFS(i.first, i.second);
                if (min_depth[i.first] > depth[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);
                    }
                }
            }
            min_depth[node] = min(min_depth[node], min_depth[i.first]);
        }
    }
    return cur;
}

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;
        if (a != b)
        {
            q[a - 1].push_back({p, 1});
            q[b - 1].push_back({p, -1});
        }
    }
    depth[0] = min_depth[0] = 0;
    DFS(0, -1);
    cout << s;
    return 0;
}

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