oj.uz

Submission #1089326

# Submission time Handle Problem Language Result Execution time Memory
1089326 2024-09-16T09:59:30 Z TrinhKhanhDung One-Way Streets (CEOI17_oneway) C++14
100 / 100
 213 ms 44352 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e5 + 10, LOG = 17;

int N, M, T, K;
vector<int> adj[MAX], nadj[MAX];
int timer, low[MAX], num[MAX], gr[MAX], h[MAX], d[MAX][LOG], in[MAX], out[MAX], tmr, ans[MAX];
ll val[MAX];
pair<int, int> edge[MAX];
vector<pair<int, int>> edges, prs;
stack<int> st;
map<pair<int, int>, int> mp, mp1;

void tarjan(int u, int p = -1){
    low[u] = num[u] = ++timer;
    st.push(u);
    for(int v: adj[u]){
        if(v == p) continue;
        if(!num[v]) tarjan(v, u);
        minimize(low[u], low[v]);
    }
    if(low[u] == num[u]){
        K++;
        while(true){
            int v = st.top(); st.pop();
            num[v] = low[v] = INF;
            gr[v] = K;
            if(v == u) break;
        }
    }
}

void dfs(int u, int p = -1){
    in[u] = ++tmr;
    edge[tmr] = make_pair(p, u);
    for(int v: nadj[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        d[v][0] = u;
        for(int i = 1; i < LOG; i++) d[v][i] = d[d[v][i - 1]][i - 1];
        dfs(v, u);
    }
    out[u] = tmr;
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int delta = h[u] - h[v];
    for(int i = 0; i < LOG; i++) if(BIT(delta, i)){
        u = d[u][i];
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) if(d[u][i] != d[v][i]){
        u = d[u][i];
        v = d[v][i];
    }
    return d[v][0];
}

void solve(){
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u, v});
    }
    cin >> T;
    for(int i = 1; i <= T; i++){
        int u, v; cin >> u >> v;
        prs.push_back({u, v});
    }

    for(int i = 1; i <= N; i++) if(!num[i]){
        tarjan(i);
    }

    for(int i = 0; i < sz(edges); i++){
        auto o = edges[i];
        mp1[make_pair(min(o.fi, o.se), max(o.fi, o.se))]++;
        int u = gr[o.fi], v = gr[o.se];
        if(u != v){
            mp[make_pair(u, v)] = i;
            nadj[u].push_back(v);
            nadj[v].push_back(u);
        }
    }
    for(int i = 1; i <= K; i++){
        cps(nadj[i]);
    }
    for(int i = 1; i <= K; i++) if(in[i] == 0){
        dfs(i);
    }
    for(auto o: prs){
        int u = gr[o.fi], v = gr[o.se];
        int p = lca(u, v);
        val[in[u]]++;
        val[in[p]]--;
        val[in[v]] += MASK(20);
        val[in[p]] -= MASK(20);
    }

    for(int i = K; i >= 1; i--){
        val[i] += val[i + 1];
    }

    for(int i = 2; i <= K; i++){
        ll c = val[in[i]] - val[out[i] + 1];
        // cout << i << ' ' << c << '\n';
        int u = d[i][0], v = i;
        if(mp.count(make_pair(u, v))){
            int id = mp[make_pair(u, v)];
            if(c >= MASK(20)) ans[id] = 1;
            else if(c >= 1) ans[id] = 2;
        }
        else{
            int id = mp[make_pair(v, u)];
            if(c >= MASK(20)) ans[id] = 2;
            else if(c >= 1) ans[id] = 1;
        }
    }

    for(int i = 0; i < sz(edges); i++){
        auto o = edges[i];
        int u = o.fi, v = o.se;
        if(mp1[make_pair(min(u, v), max(u, v))] >= 2) ans[i] = 0;
    }

    for(int i = 0; i < M; i++){
        if(!ans[i]) cout << "B";
        else if(ans[i] == 1) cout << "R";
        else cout << "L";
    }
}

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

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 1 ms 5820 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5948 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 1 ms 5820 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5948 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 73 ms 17096 KB Output is correct
12 Correct 80 ms 18164 KB Output is correct
13 Correct 83 ms 20072 KB Output is correct
14 Correct 97 ms 26820 KB Output is correct
15 Correct 105 ms 28168 KB Output is correct
16 Correct 155 ms 36612 KB Output is correct
17 Correct 146 ms 38992 KB Output is correct
18 Correct 160 ms 37064 KB Output is correct
19 Correct 127 ms 40132 KB Output is correct
20 Correct 73 ms 17708 KB Output is correct
21 Correct 66 ms 17860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 1 ms 5820 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5948 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 73 ms 17096 KB Output is correct
12 Correct 80 ms 18164 KB Output is correct
13 Correct 83 ms 20072 KB Output is correct
14 Correct 97 ms 26820 KB Output is correct
15 Correct 105 ms 28168 KB Output is correct
16 Correct 155 ms 36612 KB Output is correct
17 Correct 146 ms 38992 KB Output is correct
18 Correct 160 ms 37064 KB Output is correct
19 Correct 127 ms 40132 KB Output is correct
20 Correct 73 ms 17708 KB Output is correct
21 Correct 66 ms 17860 KB Output is correct
22 Correct 201 ms 40776 KB Output is correct
23 Correct 180 ms 38844 KB Output is correct
24 Correct 213 ms 38976 KB Output is correct
25 Correct 172 ms 44352 KB Output is correct
26 Correct 169 ms 40432 KB Output is correct
27 Correct 201 ms 39144 KB Output is correct
28 Correct 40 ms 10192 KB Output is correct
29 Correct 84 ms 19240 KB Output is correct
30 Correct 84 ms 19592 KB Output is correct
31 Correct 87 ms 19796 KB Output is correct
32 Correct 116 ms 30272 KB Output is correct