Submission #897027

#	Time	Username	Problem	Language	Result	Execution time	Memory
897027		codefox	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	122 ms	20444 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define s second
#define f first

vector<vector<pii>> graph;
vector<vector<pii>> cgraph;
vector<int> comp;
vector<int> low;
vector<int> num;
vector<bool> used;
vector<int> start;
vector<int> ende;
vector<int> dir;
vector<bool> vis;
stack<int> s;
int c = 0;
int d = 0;

void bicc(int i)
{
    vis[i] = true;
    low[i] = num[i] = c++;
    s.push(i);
    for (pii ele: graph[i])
    {
        if (used[ele.s]) continue;
        used[ele.s] = true;
        if (!vis[ele.f]) bicc(ele.f);
        low[i] = min(low[i], low[ele.f]);
    }
    if (num[i]==low[i])
    {
        while (s.size() && num[s.top()]>=num[i])
        {
            comp[s.top()] = d;
            s.pop();
        }
        d++;
    }
}

int dfs(int i)
{
    vis[i] = true;
    int path = 0;
    path -= ende[i];
    path +=start[i];
    for (pii ele:cgraph[i])
    {
        if (vis[ele.f]) continue;
        dir[ele.s] = dfs(ele.f);
        path += dir[ele.s];
        if (dir[ele.s]<0) dir[ele.s] = ele.f;
        else if (dir[ele.s]>0) dir[ele.s] = i;
        else dir[ele.s] = -1;
    }
    return path;
}


int main()
{
    int n, m;
    cin >> n >> m;
    graph = vector<vector<pii>>(n);
    comp = vector<int>(n);
    low = vector<int>(n);
    num = vector<int>(n);
    used = vector<bool>(m, false);
    vis  = vector<bool>(n, false);
    vector<pii> edges(m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
        edges[i] = {a, b};
    }
    for (int i = 0; i < n; i++) if (!vis[i]) bicc(i);

    cgraph = vector<vector<pii>>(d);
    for (int i = 0; i < n; i++)
    {
        for (pii ele: graph[i])
        {
            if (comp[i]==comp[ele.f]) continue;
            cgraph[comp[i]].push_back({comp[ele.f], ele.s});
        }
    }

    start = vector<int>(d, 0);
    ende = vector<int>(d, 0);
    dir = vector<int>(m, -1);
    vis = vector<bool>(d, false);

    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        start[comp[a]]++;
        ende[comp[b]]++;
    }

    for (int i = 0; i < d; i++)
    {
        if (vis[i]) continue;
        dfs(i);
    }

    for (int i = 0; i < m; i++)
    {
        if (dir[i]==-1) cout << 'B';
        else if (dir[i]==comp[edges[i].s]) cout << 'R';
        else if (dir[i]==comp[edges[i].f]) cout << 'L';
    }

    return 0;
}

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