oj.uz

Submission #1027263

# Submission time Handle Problem Language Result Execution time Memory
1027263 2024-07-19T02:57:41 Z anHiep One-Way Streets (CEOI17_oneway) C++14
0 / 100
 13 ms 13404 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}]);
        cebug(u, v.first, ps[v.first], v.second);
        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;
        }
    }
}
 
void solve(){
    int n, m;
    cin >> n >> m;
    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;
        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;
    cebug(nenso[18]);
    for(int i = 1; i <= p; i++){
        int u, v; cin >> u >> v;
        u = nenso[u], v= nenso[v];
        cebug(u, 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);
        }
    }
    cebug(ans[7]);
    for(int i = 1; i <= m; i++){
        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 cal(long long int, long long int)':
oneway.cpp:4:20: warning: statement has no effect [-Wunused-value]
    4 | #define cebug(...) "anHiepORZ"
      |                    ^~~~~~~~~~~
oneway.cpp:108:9: note: in expansion of macro 'cebug'
  108 |         cebug(u, v.first, ps[v.first], v.second);
      |         ^~~~~
oneway.cpp: In function 'void solve()':
oneway.cpp:4:20: warning: statement has no effect [-Wunused-value]
    4 | #define cebug(...) "anHiepORZ"
      |                    ^~~~~~~~~~~
oneway.cpp:189:5: note: in expansion of macro 'cebug'
  189 |     cebug(nenso[18]);
      |     ^~~~~
oneway.cpp:4:20: warning: statement has no effect [-Wunused-value]
    4 | #define cebug(...) "anHiepORZ"
      |                    ^~~~~~~~~~~
oneway.cpp:193:9: note: in expansion of macro 'cebug'
  193 |         cebug(u, v);
      |         ^~~~~
oneway.cpp:195:13: warning: unused variable 'l' [-Wunused-variable]
  195 |         int l = lca(u, v);
      |             ^
oneway.cpp:4:20: warning: statement has no effect [-Wunused-value]
    4 | #define cebug(...) "anHiepORZ"
      |                    ^~~~~~~~~~~
oneway.cpp:208:5: note: in expansion of macro 'cebug'
  208 |     cebug(ans[7]);
      |     ^~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 13 ms 13148 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 13 ms 13328 KB Output is correct
8 Correct 13 ms 13148 KB Output is correct
9 Incorrect 4 ms 12892 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 13 ms 13148 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 13 ms 13328 KB Output is correct
8 Correct 13 ms 13148 KB Output is correct
9 Incorrect 4 ms 12892 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 13 ms 13148 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 13 ms 13328 KB Output is correct
8 Correct 13 ms 13148 KB Output is correct
9 Incorrect 4 ms 12892 KB Output isn't correct
10 Halted 0 ms 0 KB -