Submission #994494

#	Time	Username	Problem	Language	Result	Execution time	Memory
994494		vladilius	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	600 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

struct TR{
    vector<vector<int>> g;
    vector<pii> ed;
    int n;
    TR(int ns){
        n = ns;
        g.resize(n + 1);
    }
    void add(int u, int v){
        ed.pb({u, v});
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> p, d, tin, tout;
    int timer;
    void fill(int v, int pr){
        tin[v] = ++timer;
        p[v] = pr;
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
        }
        tout[v] = timer;
    }
    vector<int> f;
    vector<bool> b;
    void build(){
        p.resize(n + 1);
        d.resize(n + 1);
        tin.resize(n + 1);
        tout.resize(n + 1);
        timer = 0;
        fill(1, 0);
        f.resize(n + 1);
        b.resize(n + 1);
        for (auto [x, y]: ed){
            // x -> y : L -> R
            if (d[x] > d[y]){
                b[x] = 1;
            }
            else {
                b[y] = 0;
            }
        }
    }
    bool check(int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    }
    int lca(int x, int y){
        while (!check(x, y)){
            x = p[x];
        }
        return x;
    }
    void set_r(int x, int l, bool i){
        while (x != l){
            int val = 1 + (b[x] ^ i);
            if (f[x] && f[x] != val){
                while (true){
                    x++;
                }
            }
            f[x] = val;
            x = p[x];
        }
    }
    void setp(int x, int y){
        int l = lca(x, y);
        set_r(x, l, 0);
        set_r(y, l, 1);
    }
    char get(int x, int y){
        if (d[x] > d[y]) swap(x, y);
        if (!f[y]) return 'B';
        return ((f[y] == 1) ? 'L' : 'R');
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<pii> g[n + 1], ed;
    for (int i = 1; i <= m; i++){
        int u, v; cin>>u>>v;
        ed.pb({u, v});
        if (u == v) continue;
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    
    vector<bool> used(n + 1);
    vector<int> t[n + 1], ind(n + 1);
    function<void(int)> dfs = [&](int v){
        used[v] = 1;
        for (auto p: g[v]){
            int i = p.ff;
            if (used[i]) continue;
            t[i].pb(v);
            t[v].pb(i);
            ind[i] = p.ss;
            dfs(i);
        }
    };
    dfs(1);
    
    vector<int> d(n + 1, -1), par(n + 1);
    function<void(int, int)> fill_d = [&](int v, int pr){
        par[v] = pr;
        for (int i: t[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill_d(i, v);
        }
    };
    fill_d(1, 0);
    
    vector<int> dp(n + 1, -1);
    vector<pii> br;
    vector<bool> ban(m + 1);
    function<void(int, int)> solve = [&](int v, int pr){
        dp[v] = 0;
        for (auto p: g[v]){
            int i = p.ff;
            if (i == pr || v == par[i]) continue;
            dp[v] += (2 * (d[i] < d[v]) - 1);
        }
        for (int i: t[v]){
            if (i == pr) continue;
            solve(i, v);
            dp[v] += dp[i];
        }
        if (!dp[v]){
            ban[ind[v]] = 1;
            if (v != 1) br.pb({v, pr});
        }
    };
    solve(1, 0);
    
    fill(used.begin(), used.end(), 0);
    
    vector<int> all[n + 1], gr(n + 1);
    int cnt = 0;
    function<void(int)> dfs1 = [&](int v){
        all[cnt].pb(v);
        gr[v] = cnt;
        used[v] = 1;
        for (auto [i, ii]: g[v]){
            if (used[i] || ban[ii]) continue;
            dfs1(i);
        }
    };
    
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            cnt++;
            dfs1(i);
        }
    }

    TR T(cnt);
    assert((cnt == (br.size() + 1)));
    map<pii, bool> mp;
    for (auto [x, y]: br){
        x = gr[x]; y = gr[y];
        mp[{x, y}] = 1;
        T.add(x, y);
    }
    T.build();
    
    int q; cin>>q;
    for (int i = 1; i <= q; i++){
        int x, y; cin>>x>>y;
        x = gr[x]; y = gr[y];
        if (x != y) T.setp(x, y);
    }

    for (auto [x, y]: ed){
        x = gr[x]; y = gr[y];
        if (x == y){
            cout<<'B';
            continue;
        }
        assert((mp.find({x, y}) != mp.end() || mp.find({y, x}) != mp.end()));
        cout<<T.get(x, y);
    }
    cout<<"\n";
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from oneway.cpp:1:
oneway.cpp: In function 'int main()':
oneway.cpp:174:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     assert((cnt == (br.size() + 1)));
      |             ~~~~^~~~~~~~~~~~~~~~~~

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