Submission #1280130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280130		cokalhado	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	332 KiB

oneway

// https://oj.uz/problem/view/CEOI17_oneway
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
int n, m, P;
vector<pair<int, int>> g[maxn];
bool f[maxn];
int d[maxn];
int dp[maxn];
int pai[maxn];
char ans[maxn];
pair<int, int> io[maxn];
int T;
set<pair<int, int>> in;
set<pair<int, int>> closed;
map<pair<int, int>, int> ruas;
pair<int, int> sp[maxn];
pair<int, int> tr[4*maxn]; // max min

pair<int, int> merge(pair<int, int> a, pair<int, int> b)
{
    return {max(a.first, b.first), min(a.second, b.second)};
}

void build(int no, int l, int r)
{
    if(l == r) tr[no] = {-maxn, maxn};
    else
    {
        int lc = 2*no; int rc = 2*no+1; int mid = (l+r)/2;
        build(lc, l, mid);
        build(rc, mid+1, r);
        tr[no] = merge(tr[lc], tr[rc]);
    }
}

void update(int no, int l, int r, int pos, int val)
{
    if(l == r) tr[no] = merge(tr[no], {val, val});
    else
    {
        int lc = 2*no; int rc = 2*no+1; int mid = (l+r)/2;
        if(pos <= mid) update(lc, l, mid, pos, val);
        else update(rc, mid+1, r, pos, val);
        tr[no] = merge(tr[lc], tr[rc]);
    }
}

pair<int, int> query(int no, int l, int r, int L, int R)
{
    if(r < L || R < l) return {-maxn, maxn};
    else if(L <= l && r <= R) return tr[no];
    else
    {
        int lc = 2*no; int rc = 2*no+1; int mid = (l+r)/2;
        return merge(query(lc, l, mid, L, R), query(rc, mid+1, r, L, R));
    }
}

void dfs(int x, int ant)
{
    io[x].first = ++T;
    f[x] = 1;
    for(auto[i, t] : g[x])
    {
        if(i == ant) continue;
        if(f[i])
        {
            ans[t] = 'B';
            if(d[i] > d[x]) dp[x]--;
            else dp[x]++;
            continue;
        }
        d[i] = d[x]+1;
        pai[i] = x;
        dfs(i, x);
        dp[x] += dp[i];
    }
    io[x].second = T;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        if(a == b) ans[i] = 'B';
        else if(in.count({a, b}) || in.count({b, a}))
        {
            ans[i] = 'B';
            closed.insert({a, b});
            closed.insert({b, a});
        }
        else
        {
            in.insert({a, b});
            ruas[{a, b}] = i;
            ruas[{b, a}] = i;
        }
    }

    for(auto[a, b] : in)
    {
        int i = ruas[{a, b}];
        if(closed.count({a, b})) ans[i] = 'B';
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    dfs(1, 0);
    pai[1] = 1;

    cin >> P;
    for(int i = 0; i < P; i++)
    {
        int a, b;
        cin >> a >> b;
        sp[i] = {a, b};
    }

    build(1, 1, T);
    for(int i = 0; i < P; i++)
    {
        auto[a, b] = sp[i];
        update(1, 1, T, io[a].first, io[b].first);
    }

    for(int i = 2; i <= n; i++)
    {
        int p = pai[i];
        int j = ruas[{p, i}];
        if(ans[j] == 'B' || ans[j] == 'L' || ans[j] == 'R') continue;
        if(dp[i] != 0)
        {
            ans[j] = 'B';
            continue;
        }
        pair<int, int> x = query(1, 1, T, io[i].first, io[i].second);
        if(x.first > io[i].second || x.second < io[i].first)
        {
            ans[j] = 'R';
        }
    }

    build(1, 1, T);
    for(int i = 0; i < P; i++)
    {
        auto[a, b] = sp[i];
        update(1, 1, T, io[b].first, io[a].first);
    }

    for(int i = 2; i <= n; i++)
    {
        int p = pai[i];
        int j = ruas[{p, i}];
        if(ans[j] == 'B' || ans[j] == 'L' || ans[j] == 'R') continue;
        if(dp[i] != 0)
        {
            ans[j] = 'B';
            continue;
        }
        pair<int, int> x = query(1, 1, T, io[i].first, io[i].second);
        if(x.first > io[i].second || x.second < io[i].first)
        {
            ans[j] = 'L';
        }
        else ans[j] = 'B';
    }

    string gans;
    for(int i = 1; i <= m; i++)
    {
        gans += ans[i];
    }
    cout << gans;
    return 0;
}

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