oj.uz

Submission #1027532

# Submission time Handle Problem Language Result Execution time Memory
1027532 2024-07-19T07:21:08 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 811 ms 112736 KB 
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "anHiepORZ"
#endif

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back


#define int long long

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

vector<int> g[N];
vector<pair<int,int>> t[N];
map<pair<int,int>,int> bridge;
int vis[N];
int tin[N], low[N];
int timedfs = 0;

void dfs(int u, int p = 0){
    timedfs++;
    low[u] = tin[u] = timedfs;
    for(int v : g[u]){
        if(v == p) continue;
        if(tin[v] == 0){
            dfs(v, u);
            if(low[v] == tin[v]){
                // int _u = u, _v = v.first;
                // if(_v < _u) swap(u)
                bridge[make_pair(u, v)] = 1;
                bridge[make_pair(v, u)] = 1;
            }
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }
}
// vector<int> edge;
// int cnt;
// map<pair<int,int>, int> dm;
int nenso[N];
int ans[N];
int idx;

void dfs2(int u){
    nenso[u] = idx;
    for(int v: g[u]){
        if(bridge[{u, v}]) continue;
        if(vis[v]) continue;
        vis[v] = 1;
        dfs2(v);
    }
}

int up[N][20], h[N], ps[N];
int vv[N];

void dfs3(int u, int p = 0, int hh = 0){
    h[u]= hh;
    for(auto v: t[u]){
        if(v.first == p) continue;
        vv[v.first] = 1;
        up[v.first][0] = u;
        for(int i = 1; i < 20; i++){
            up[v.first][i] = up[up[v.first][i - 1]][i - 1];
        }
        dfs3(v.first, u, hh + 1);
    }
}

int lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    int diff = h[v] - h[u];
    for(int i = 0; i < 20; i++){
        if(diff & (1<<i)) v = up[v][i];
    }
    if(u == v) return u;
    // cebug(u, v);
    for(int i = 19; i >= 0; i--){
        int _u = up[u][i], _v = up[v][i];
        if(_u != _v) u = _u, v = _v;
    }
    return up[u][0];
}

map<pair<int,int>,int> dit;
void cal(int u, int p = 0){
    for(auto v: t[u]){
        if(v.first == p) continue;
        vv[v.first]=1;
        cal(v.first, u);
        ps[u] += ps[v.first];
    }
    for(auto v: t[u]){
        if(v.first == p) continue;
        // cebug(u, v.first, dit[{u, v.first}]);

        if(ps[v.first] == 0) ans[v.second] = 1;
        else if(ps[v.first] > 0){
            if(dit[{u, v.first}]) ans[v.second] = 2;
            else ans[v.second] = 3;
        }
        else{
            if(dit[{u, v.first}]) ans[v.second] = 3;
            else ans[v.second] = 2;
        }
    }
}

map<pair<int,int>,int> lon;
vector<pair<int,int>> cc;

void solve(){
    int n, m;
    cin >> n >> m;
    cc.resize(m + 1);
    vector<pair<pair<int,int>, int>> e;
    map<pair<int,int>, int> qr;
    map<pair<int,int>, int> dm;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        lon[{u, v}]++;
        lon[{v, u}]++;
        cc[i] = {u, v};
        if(u == v){
            continue;
        }
        dm[{u, v}] = 1;
        qr[{u, v}] = i;
        qr[{v, u}] = i;
        g[u].push_back(v);
        g[v].push_back(u);
        e.push_back({make_pair(u, v), i});
    }

    //ans 1: B, 2: R, 3: L

    for(int i = 1; i <= n; i++){
        if(tin[i] == 0) dfs(i);
    }

    map<pair<int,int>, int> sus;
    for(auto &x : e){
        if(bridge[x.first] == 0) ans[x.second] = 1;
        else{
            int _u = x.first.first, _v = x.first.second;
            if(_v < _u) swap(_u, _v);
            if(sus[{_u, _v}] == 1) ans[x.second] = 1; 
            sus[{_u, _v}] = 1;
        }
    }

    idx = 1;
    for(int i = 1; i <= n; i++){
        if(vis[i] == 0){
            vis[i] = 1;
            dfs2(i);
            //edge
            idx++;
        }
    }

    for(auto b : bridge){
        if(b.second == 0) continue;

        int _u = b.first.first, _v = b.first.second;
        if(_v < _u) swap(_u, _v);
        if(sus[{_u, _v}] > 1) continue;
        //cerr << nenso[b.first.first] << " " << nenso[b.first.second] << endl;
        if(dm[b.first]) dit[{nenso[b.first.first], nenso[b.first.second]}] = 1;
        t[nenso[b.first.first]].push_back({nenso[b.first.second], qr[b.first]});
    }

    // for(int i = 1; i <= idx; i++){
    //     cebug(i, t[i]);
    // }

    for(int i = 1; i <= idx; i++){
        if(vv[i] == 0){
            vv[i] = 1;
            dfs3(i);
        }
    }

    int p;
    cin >> p;
    for(int i = 1; i <= p; i++){
        int u, v; cin >> u >> v;
        u = nenso[u], v= nenso[v];

        if(u == v) continue;
        int l = lca(u, v);
        // cebug(u, v, l);
        //u->l 
        ps[u]++;
        ps[v]--;  
    }
    memset(vv, 0, sizeof(vv));
    for(int i = 1; i <= idx; i++){
        if(vv[i] ==0){
            vv[i] = 1;
            cal(i);
        }
    }
    for(int i = 1; i <= m; i++){
        if(lon[cc[i]] >= 2){
            cout << "B";
            continue;
        }
        if(ans[i] == 1 || ans[i] == 0) cout << "B";
        else if(ans[i] == 2) cout << "L";
        else cout << "R";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tc; tc = 1;
    while(tc--)
        solve();
 
    return 0;
}

Compilation message

oneway.cpp: In function 'void solve()':
oneway.cpp:204:13: warning: unused variable 'l' [-Wunused-variable]
  204 |         int l = lca(u, v);
      |             ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 6 ms 13288 KB Output is correct
4 Correct 6 ms 13384 KB Output is correct
5 Correct 5 ms 13404 KB Output is correct
6 Correct 4 ms 12988 KB Output is correct
7 Correct 6 ms 13404 KB Output is correct
8 Correct 6 ms 13400 KB Output is correct
9 Correct 7 ms 13148 KB Output is correct
10 Correct 7 ms 13148 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 6 ms 13288 KB Output is correct
4 Correct 6 ms 13384 KB Output is correct
5 Correct 5 ms 13404 KB Output is correct
6 Correct 4 ms 12988 KB Output is correct
7 Correct 6 ms 13404 KB Output is correct
8 Correct 6 ms 13400 KB Output is correct
9 Correct 7 ms 13148 KB Output is correct
10 Correct 7 ms 13148 KB Output is correct
11 Correct 572 ms 65792 KB Output is correct
12 Correct 636 ms 67164 KB Output is correct
13 Correct 548 ms 69524 KB Output is correct
14 Correct 682 ms 78052 KB Output is correct
15 Correct 593 ms 81920 KB Output is correct
16 Correct 720 ms 102884 KB Output is correct
17 Correct 595 ms 106752 KB Output is correct
18 Correct 686 ms 102404 KB Output is correct
19 Correct 653 ms 108544 KB Output is correct
20 Correct 405 ms 66748 KB Output is correct
21 Correct 335 ms 64516 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 6 ms 13288 KB Output is correct
4 Correct 6 ms 13384 KB Output is correct
5 Correct 5 ms 13404 KB Output is correct
6 Correct 4 ms 12988 KB Output is correct
7 Correct 6 ms 13404 KB Output is correct
8 Correct 6 ms 13400 KB Output is correct
9 Correct 7 ms 13148 KB Output is correct
10 Correct 7 ms 13148 KB Output is correct
11 Correct 572 ms 65792 KB Output is correct
12 Correct 636 ms 67164 KB Output is correct
13 Correct 548 ms 69524 KB Output is correct
14 Correct 682 ms 78052 KB Output is correct
15 Correct 593 ms 81920 KB Output is correct
16 Correct 720 ms 102884 KB Output is correct
17 Correct 595 ms 106752 KB Output is correct
18 Correct 686 ms 102404 KB Output is correct
19 Correct 653 ms 108544 KB Output is correct
20 Correct 405 ms 66748 KB Output is correct
21 Correct 335 ms 64516 KB Output is correct
22 Correct 745 ms 107848 KB Output is correct
23 Correct 798 ms 105472 KB Output is correct
24 Correct 811 ms 105792 KB Output is correct
25 Correct 742 ms 112736 KB Output is correct
26 Correct 767 ms 107284 KB Output is correct
27 Correct 653 ms 105292 KB Output is correct
28 Correct 137 ms 19516 KB Output is correct
29 Correct 406 ms 65916 KB Output is correct
30 Correct 393 ms 65988 KB Output is correct
31 Correct 392 ms 67032 KB Output is correct
32 Correct 448 ms 77308 KB Output is correct