Submission #518207

#	Time	Username	Problem	Language	Result	Execution time	Memory
518207		blue	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	234 ms	35912 KiB

oneway

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

const int mx = 100'000;


int n, m;

vi edge[1+mx];

vi nw_edge[1+mx];
vi nw_rev[1+mx];

vi visit(1+mx, 0);

vi ee;

void dfs(int u, int p)
{
    visit[u] = 1;
    for(int v: edge[u])
    {
        if(v == p) continue;

        if(visit[v])
        {
            // cerr << v << " ->* " << u << '\n';
            nw_edge[v].push_back(u);
            nw_rev[u].push_back(v);
        }
        else
        {
            // cerr << u << " -> " << v << '\n';
            nw_edge[u].push_back(v);
            nw_rev[v].push_back(u);
            dfs(v, u);
        }
    }

    ee.push_back(u);
}


vi bcc(1+mx, 0);
int ct = 0;
vi bcc_list[1+mx];

void dfs2(int u)
{
    bcc[u] = ct;
    bcc_list[ct].push_back(u);
    for(int v: nw_rev[u])
    {
        if(bcc[v]) continue;
        dfs2(v);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    vi a(1+m), b(1+m);

    for(int e = 1; e <= m; e++)
    {
        cin >> a[e] >> b[e];
        edge[a[e]].push_back(b[e]);
        edge[b[e]].push_back(a[e]);
    }


    for(int u = 1; u <= n; u++)
    {
        if(visit[u]) continue;
        dfs(u, 0);
    }

    // for(int u = 1; u <= n; u++)
    // {
    //     cerr << u << " : ";
    //     for(int v: nw_edge[u]) cerr << v << ' ';
    //     cerr << '\n';
    // }

    reverse(ee.begin(), ee.end());

    for(int u: ee)
    {
        if(bcc[u]) continue;
        ++ct;
        dfs2(u);
    }


    // for(int i = 1; i <= ct; i++)
    // {
    //     for(int u: bcc_list[i]) cerr << u << ' ';
    //     cerr << '\n';
    // }

    vector<pii> bcc_edge[1+ct];
    vi deg(1+ct, 0);

    vector<char> ans(1+m, 'B');

    for(int e = 1; e <= m; e++)
    {
        if(bcc[a[e]] == bcc[b[e]])
        {
            continue;
        }

        bcc_edge[ bcc[a[e]] ].push_back({bcc[b[e]], +e});
        bcc_edge[ bcc[b[e]] ].push_back({bcc[a[e]], -e});
        deg[bcc[a[e]]]++;
        deg[bcc[b[e]]]++;
    }







    vi score(1+ct, 0);

    int p;
    cin >> p;

    for(int z = 1; z <= p; z++)
    {
        int x, y;
        cin >> x >> y;

        score[bcc[x]]++;
        score[bcc[y]]--;
    }

    fill(visit.begin(), visit.end(), 0);

    queue<int> tbv;

    for(int u = 1; u <= ct; u++)
    {
        if(deg[u] == 1)
        {
            tbv.push(u);
        }
    }

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        deg[u] = -5;

        // cerr << "u = " << u << " : ";
        // for(int w: bcc_list[u]) cerr << w << ' ';
        // cerr << '\n';

        for(pii e: bcc_edge[u])
        {
            int v = e.first;
            int id = e.second;

            if(deg[v] < 0) continue;

            deg[v]--;

            // cerr << "par " << u << " = " << v << '\n';
            // cerr << score[u] << '\n';

            if(score[u] > 0)
            {
                // cerr << "#\n";
                if(id > 0)
                    ans[id] = 'R';
                else
                    ans[-id] = 'L';
            }
            else if(score[u] < 0)
            {
                // cerr << "? " << id << '\n';
                if(id > 0)
                    ans[id] = 'L';
                else
                    ans[-id] = 'R';
            }

            score[v] += score[u];
            score[u] = 0;

            if(deg[v] == 1) tbv.push(v);
        }
    }

    for(int e = 1; e <= m; e++) cout << ans[e];
    cout << '\n';
}

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