Submission #914209

#	Time	Username	Problem	Language	Result	Execution time	Memory
914209		sleepntsheep	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	8 ms	33112 KiB

oneway

#include <stack>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int n, m, p;
basic_string<pair<int, int>> g[N];

int tin[N], low[N], timer; char ans[N];
int grp[N], twoedgecc;

stack<int> sd;

void tarjan(int u, int p)
{
    tin[u] = low[u] = ++timer;
    sd.push(u);

    int parallel = 0;
    for (auto [v, eid] : g[u])
    {
        if (v == p && !parallel)
        {
            parallel = 1;
            continue;
        }
        if (!tin[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }

    if (tin[u] == low[u])
    {
        //cout<<"NEWCOM " << twoedgecc<<'\n';
        while (sd.top() != u)
        {
            grp[sd.top()] = twoedgecc;
            //cout<<sd.top()<<" ";
            sd.pop();
        }
        grp[sd.top()] = twoedgecc++;
            //cout<<sd.top()<<"\n";
        sd.pop();
    }
}

basic_string<pair<int, int>> G[N];

int aux[N], sz[N], ch[N], ci[N], P[20][N], hv[N], hveid[N], dep[N];

void dfs(int u, int p)
{
    sz[u] = 1;
    P[0][u] = p;
    for (int j = 1; j < 18; ++j) P[j][u] = P[j-1][P[j-1][u]];
    int hvsz = -1;
    for (auto [v, _] : G[u]) if (v != p)
    {
        dep[v] = dep[u] + 1;
        dfs(v, u), sz[u] += sz[v];
        if (sz[v] > hvsz) hv[u] = v, hvsz = sz[v], hveid[u] = _;
    }
}

int ctimer;
void hld(int u, int h, int pd)
{
    ci[u] = ctimer++; ch[u] = h;
    aux[u] = pd;
    if (hv[u]) hld(hv[u], h, hveid[u]);
    for (auto [v, _] : G[u]) if (v != P[0][u] and v != hv[u]) hld(v, v, _);
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(v, u);
    int dt = dep[u] - dep[v];
    for(int j=18;j--;)if(dt&(1<<j))u=P[j][u];
    if(u==v)return u;
    for(int j=18;j--;)if(P[j][u]-P[j][v])u=P[j][u],v=P[j][v];
    return P[0][u];
}

int kth(int u, int k)
{
    for (int j=18;j--;)if(k&(1<<j)) u=P[j][u];
    return u;
}

int what[N];
void updup(int u, int a, int d)
{
    //cout << "UPDUP " << u << ' ' << a << ' ' << char(d)<<'\n';
    for (; ch[u] != ch[a]; u = P[0][ch[u]])
    {
        what[ci[ch[u]]] = d;
        what[ci[u]] = -1;
    }
    what[ci[a]] = d;
    what[ci[u]] = -1;
}



int main()
{
    ShinLena;
    cin >> n >> m;
    for (int u, v, i = 1; i <= m; ++i)
        cin >> u >> v, g[u].push_back({v, i}), g[v].push_back({u, -i}), ans[i] = 'B';

    for (int i = 1; i <= n; ++i) if (!tin[i]) tarjan(i, -1);

    for (int i = 1; i <= n; ++i)
        for (auto [v, eid] : g[i])
            if (eid > 0 and grp[i] != grp[v])
                G[grp[i]].push_back({grp[v], eid}), G[grp[v]].push_back({grp[i], -eid});

    for (int i = 0; i < twoedgecc; ++i)
        sort(ALL(G[i])), G[i].resize(unique(ALL(G[i])) - G[i].begin());

    dfs(0, 0);
    hld(0, 0, 0);

    cin >> p;
    for (int x, y, i = 0; i < p; ++i)
    {
        cin >> x >> y;
        if ((x = grp[x]) == (y = grp[y])) continue;
        int a = lca(x, y);
        if (x != a) updup(x, kth(x, dep[x] - dep[a] - 1), 'R');
        if (y != a) updup(y, kth(y, dep[y] - dep[a] - 1), 'R');
    }

    for (int i = 0, running = 'B'; i < ctimer; ++i)
    {
        int T = what[i];
        if (what[i] > 0) running = what[i];
        what[i] = running;
        if (T == -1) running = 'B';
    }

    for (int i = 1; i < twoedgecc; ++i)
    {
        //cout << i << ' ' << aux[i] <<' '<<char(what[ci[i]])<<'\n';
        ans[abs(aux[i])] = what[ci[i]];
        if (aux[i] < 0)
        {
            aux[i] *= -1;
            if (ans[aux[i]] == 'L') ans[aux[i]] = 'R';
            else if (ans[aux[i]] == 'R') ans[aux[i]] = 'L';
        }
    }

    cout << (ans+1);


    return 0;
}

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