Submission #1259805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259805		phatdu12345	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	52 ms	21828 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
#define space endl << "---------debug---------" << endl
typedef pair<long, int> li;
typedef pair<long, li> loli;

int scc[MAXN], f[MAXN], n, m, low[MAXN], id[MAXN], dfstime, cnt, t;
bool mark[MAXN];
stack <int> st;
vector <pair<int, int>> a[MAXN];
string ans;

struct info{
    int u, idx, direction;
};
vector <info> tree[MAXN];

struct edges{
    int x, y, idx;
};
vector <edges> edge;

template <class X, class Y>
    bool minimize(X &a, const Y &b){
        if(a > b){
            a = b;
            return 1;
        }
        return 0;
    }

void dfsTarjan(int u, int p){

    low[u] = id[u] = ++dfstime;
    st.push(u);
    mark[u] = 1;

    for(auto i : a[u]){

        int v = i.first;
        int idx = i.second;

        if(idx == p) continue;

        if(!id[v]){
            dfsTarjan(v, idx);
            minimize(low[u], low[v]);
        }

        else
            minimize(low[u], id[v]);
    }
    if(low[u] == id[u]){
        int v;
        cnt++;
        do{
            v = st.top();
            st.pop();
            scc[v] = cnt;
        }while(v != u);
    }
}


void dfsDP(int u, int p){
    mark[u] = 1;
    for(auto i : tree[u]){

        int v = i.u;
        int idx = i.idx;
        int dir = i.direction;

        if(v == p) continue;
        dfsDP(v, u);
        f[u] += f[v];
        if(f[v] > 0)
            ans[idx] = (dir ? 'R' : 'L');
        if(f[v] < 0)
            ans[idx] = (dir ? 'L' : 'R');
    }
}


signed main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    //freopen("oneway.inp", "r", stdin);
    //freopen("oneway.out", "w", stdout);

    cin >> n >> m;
    edge.reserve(n + 5);

    for(int i = 1; i <= m; i++) ans += 'B';

    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        a[x].push_back({y, i});
        a[y].push_back({x, i});
        edge.push_back({x, y, i - 1});
    }

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

    for(auto i : edge){
            int x = i.x;
            int y = i.y;
            int idx = i.idx;

        if(scc[x] != scc[y]){
            int u = scc[x];
            int v = scc[y];
            tree[u].push_back({v, idx, 1});
            tree[v].push_back({u, idx, 0});
        }
    }

    cin >> t;
    while(t--){
        int x, y;
        cin >> y >> x;
        x = scc[x];
        y = scc[y];

        f[x]++;
        f[y]--;
    }

    fill(mark + 1, mark + 1 + n, 0);
    for(int i = 1; i <= cnt; i++) if(!mark[i]) dfsDP(i, -1);

    cout << ans;
}
/*
Idea:
f[u] là số cạnh cần đi qua cạnh nối với đỉnh u, tức là (theo tính chất cây thì mỗi đỉnh sẽ quản lí cạnh trên của nó):
       (1)
        \
         \
          \
         (u)

f[u] < 0 thì đang đi ngược chiều mà trong cái chiều u -> v với u, v là các cặp đỉnh trong truy vấn
f[u] > 0 thì đi đúng chiều

TH cùng chiều thì sao mà ngược chiều thì sao thì tự snghi để xử lí vì khá đơn giản

Tính chất và phản biện: xét tại đỉnh u, nếu đường đi x -> y sao cho x hay y thuộc cây con gốc u thì:
1 là nó sẽ bị khử bởi lca(x, y) với h[lca(x, y] <= h[u], thì hướng của chúng như nào cũng được.

2 là có 1 trong 2 đỉnh có độ cao thấp hơn (tức ở trên cao hơn) thì 1 là chiều từ max(h[x], h[y]) nó đi theo chiều u đi xuống, 2 là ngược lại
, còn cách đỉnh đi qua u cũng vậy, nó bắt buộc phải CÙNG CHIỀU ==> 1 là nó luôn tăng, 2 là luôn giảm và rồi bị khử bởi LCA, nếu mà tăng rồi giảm thì tức là 1 cạnh cần 2 chiều mới thoả
==> ko tồn tại TH như vậy vì đề luôn đảm bảo có đáp án hợp lệ
*/

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