Submission #1226075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226075		giorgi123glm	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	0 ms	320 KiB

oneway

#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
using namespace std;

#define int long long

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0, M = 0;
    cin >> N >> M;

    vector <vector <int> > gr (N + 1);
    vector <pair <int, int> > in_v (M + 1);
    map <pair <int, int>, int> revin;
    for (int i = 1; i <= M; i++) {
        int a = 0, b = 0;
        cin >> a >> b;

        revin[{a, b}] = i;
        revin[{b, a}] = i;
        in_v[i] = {a, b};

        gr[a].emplace_back (b);
        gr[b].emplace_back (a);
    }

    // Step 1, depth
    vector <int> depth (N + 1);
    vector <vector <int> > depth_v (N + 1);
    vector <bool> been (N + 1);
    function <void(int, int)> dfs0 =
    [&](int p, int dep) {
        depth[p] = dep;
        depth_v[dep].emplace_back (p);
        been[p] = 1;
        for (int& e : gr[p])
            if (!been[e])
                dfs0 (e, dep + 1);
    };
    dfs0 (1, 1);

    map <pair <int, int>, bool> m;
    been = vector <bool> (N + 1);
    vector <int> up (N + 1);
    function <void(int, int)> dfs1 =
    [&](int p, int par) {
        been[p] = 1;
        for (int& e : gr[p])
            if (!been[e]) {
                dfs1 (e, p);
                up[p] += up[e];
            } else if (depth[e] < depth[par]) {
                up[e]--;
                up[p]++;
            }

        if (up[p] == 0)
            m[{par, p}] = m[{p, par}] = 1;    };
    dfs1 (1, 0);
    
    been = vector <bool> (N + 1);
    vector <vector <int> > binlift (
        N + 1,
        vector <int> (20)
    );
    vector <int> in (N + 1);
    vector <int> out (N + 1);
    out[0] = 2e9;
    int timer = 1;

    function <void(int,int)> dfs2 =
    [&](int p, int par) {
        in[p] = out[p] = ++timer;
        been[p] = 1;

        binlift[p][0] = par;
        for (int i = 1; i < 20; i++)
            binlift[p][i] = binlift[
                binlift[p][i - 1]
            ][i - 1];

        for (int& e : gr[p])
            if (!been[e])
                dfs2 (e, p);

        out[p] = timer;
    };

    auto is_ancestor = [&in, &out](int a, int b) {
        return in[a] <= in[b] && in[b] <= out[a];
    };

    dfs2 (1, 0);

    auto lca = [&](int a, int b) {
        if (is_ancestor (a, b))
            return a;
        if (is_ancestor (b, a))
            return b;

        for (int p = 19; p >= 0; p--)
            if (!is_ancestor (binlift[a][p], b))
                a = binlift[a][p];

        return binlift[a][0];
    };

    vector <int> up_pref (N + 1);
    vector <int> down_pref (N + 1);

    int Q = 0;
    cin >> Q;

    while (Q--) {
        int a = 0, b = 0;
        cin >> a >> b;

        int c = lca (a, b);

        // cout << "LCA " << a << ' ' << b << ' ' << c << '\n';

        up_pref[a]++;
        up_pref[c]--;
        down_pref[b]++;
        down_pref[c]--;
    }

    string ans (M, '.');

    // for (int i = 1; i <= N; i++)
    //     cout << i << ' ' << up_pref[i] << ' ' << down_pref[i] << '\n';

    for (int i = N; i >= 1; i--)
        for (int& e : depth_v[i]) {
            if (binlift[e][0] != 0) {
                if (up_pref[e] >= 1) {
                    int ind = revin[{e, binlift[e][0]}];
                    pair <int, int> p = in_v[ind];

                    if (p == (pair <int, int>){e, binlift[e][0]})
                        ans[ind - 1] = 'R';
                    else
                        ans[ind - 1] = 'L';
                }

                if (down_pref[e] >= 1) {
                    int ind = revin[{e, binlift[e][0]}];
                    pair <int, int> p = in_v[ind];
                    if (p == (pair <int, int>){e, binlift[e][0]})
                        ans[ind - 1] = 'L';
                    else
                        ans[ind - 1] = 'R';
                }
            }

            up_pref[binlift[e][0]] += up_pref[e]; 
            down_pref[binlift[e][0]] += down_pref[e]; 
        }
    
    for (int i = 1; i <= M; i++)
        if (!m[in_v[i]])
            ans[i - 1] = 'B';

    cout << ans << '\n';
}

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