oj.uz

Submission #971360

# Submission time Handle Problem Language Result Execution time Memory
971360 2024-04-28T11:55:46 Z efedmrlr One-Way Streets (CEOI17_oneway) C++17
30 / 100
 55 ms 16468 KB 
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int LGN = 20;


struct DifArr {
    vector<int> st;
    int n;
    void reset(int nn) {
        n = nn;
        st.assign(n + 3, 0);
    }
    void update(int l, int r) {
        st[l]++; st[r + 1]--;
    }
    void get_arr() {
        for(int i = 1; i <= n; i++) {
            st[i] += st[i - 1];
        }
    }
};


int n, m;
vector<array<int, 2> > edg(N);
vector<char> res(N, '$');
struct Bridge {
    vector<vector<array<int, 2> > > adj;
    vector<int> tin, low;
    vector<bool> isBr;
    int tim = 0;
    int curc = 0;
    Bridge() {
        tin.assign(N, -1);
        low.assign(N, 0);
        isBr.assign(N, 0);
        adj.assign(N, vector<array<int, 2> >());

    }
    void dfs(int node, int pedg) {
        tin[node] = low[node] = tim++;
        for(auto c : adj[node]) {
            if(c[1] == pedg) continue;
            if(tin[c[0]] != -1) {
                low[node] = min(low[node], tin[c[0]]);
            }
            else {
                dfs(c[0], c[1]);
                low[node] = min(low[node], low[c[0]]);
                if(low[c[0]] > tin[node]) {
                    //bridge found
                    isBr[c[1]] = 1;
                }
            }
        }
    }
    
    void dfs2(int node, int par, vector<int> &comp) {
        for(auto c : adj[node]) {
            if(c[0] == par) continue;
            if(comp[c[0]] != -1) {
                continue;
            }
            if(isBr[c[1]]) {
                comp[c[0]] = curc++;
                dfs2(c[0], node, comp);
            }
            else {
                comp[c[0]] = comp[node];
                dfs2(c[0], node, comp);
            }
        }
    }
    void find_comp(vector<int> &comp) {
        curc = 0;
        comp.assign(n + 1, -1);
        for(int i = 1; i <= n; i++) {
            if(comp[i] != -1) continue;
            comp[i] = curc++;
            dfs2(i, i, comp);
        }
    }

};


struct Tre {
    vector<vector<array<int, 2> > > adj;
    vector<int> head;
    vector<int> subt, dep, tin;
    vector<int> p, pedg;
    int tim;
    int n;
    DifArr st1, st2;
    Tre() {
        adj.assign(N, vector<array<int, 2> >());
        subt.assign(N, -1);
        dep.assign(N, 0);
        tin.assign(N, 0);
        p.assign(N, 0);
        head.assign(N, 0);
        pedg.assign(N, m);
        
    }
    void dfssz(int node) {
        subt[node] = 1;
        for(auto &c : adj[node]) {
            p[c[0]] = node; pedg[c[0]] = c[1];
            adj[c[0]].erase(find(all(adj[c[0]]), array<int,2>({node, c[1]})));
            dfssz(c[0]);
            subt[node] += subt[c[0]];
            if(subt[adj[node][0][0]] < subt[c[0]]) {
                swap(adj[node][0], c);
            }
        }
    }
    void dfshld(int node) {
        tin[node] = tim++;
        for(auto c : adj[node]) {
            head[c[0]] = (c == adj[node][0]) ? head[node] : c[0];
            dep[c[0]] = dep[node] + 1;
            dfshld(c[0]); 
        }
    }   
    int lca(int x, int y) {
        while(head[x] != head[y]) {
            if(dep[head[x]] < dep[head[y]]) swap(x, y);
            x = p[head[x]];
        }
        if(dep[x] < dep[y]) {
            swap(x, y);
        }
        return y;
    }
    void init(int curc) {
        n = curc;
        for(int i = 0; i < n; i++) {
            if(subt[i] != -1) continue;
            dep[i] = tim = 0; dfssz(i);
            head[i] = i; dfshld(i);
        }
        st1.reset(n + 2);
        st2.reset(n + 2);
    }
    void upd(int x, int lc, DifArr &st) { // dep[lc] < dep[x]
    // DONT UPD LCA
        while(head[x] != head[lc]) {
            st.update(tin[head[x]], tin[x]);
            x = p[head[x]];
        }
        if(lc == x) return;
        st.update(tin[lc] + 1, tin[x]);
    }
    

};


void solve() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> edg[i][0] >> edg[i][1];
    }
    Bridge br;
    for(int i = 0; i < m; i++) {
        br.adj[edg[i][0]].pb({edg[i][1], i});
        br.adj[edg[i][1]].pb({edg[i][0], i});
    }
    for(int i = 1; i<=n; i++) {
        if(br.tin[i] != -1) continue;
        br.dfs(i, m);  
    }
    vector<int> cmp;
    br.find_comp(cmp);
    // for(int i = 0; i < m; i++) {
    //     if(br.isBr[i]) {
    //         cout << "i:" << i << " a:" << edg[i][0] << " b:" << edg[i][1] << "\n";
    //     }
    // }
    // for(int i = 1; i <= n; i++) {
    //     cout << cmp[i] << " ";
    // }
    // cout << endl;
    Tre t;
    
    for(int i = 0; i < m; i++) {
        if(!br.isBr[i]) {
            // cout << "not bridge:" << i << "\n";
            res[i] = 'B';
        }
        else {
            edg[i] = {cmp[edg[i][0]], cmp[edg[i][1]]};
            t.adj[edg[i][0]].pb({edg[i][1], i});
            t.adj[edg[i][1]].pb({edg[i][0], i});
            // cout << edg[i][0] << " " << edg[i][1] << "\n";
        }
    }
    t.init(br.curc);
    // for(int i = 0; i < br.curc; i++) {
    //     cout << "i:" << i <<" p:" << t.p[i] << "pedg:" << t.pedg [i] << endl;
    // }
    int p;
    cin >> p;
    REP(i, p) {
        int x, y;
        cin >> x >> y;
        x = cmp[x]; y = cmp[y];
        if(x == y) continue;
        int lc = t.lca(x, y);
        // cout << "x:" << x << " y:" << y << " lca:" << lc << "\n";
        t.upd(x, lc, t.st1);
        t.upd(y, lc, t.st2);
    }
    t.st1.get_arr();
    t.st2.get_arr();
    for(int i = 1; i < br.curc; i++) {
        int cur = t.pedg[i];
        // cout << "curc:" << i << " vals: ";
        // cout << t.st1.st[t.tin[i]] << " " << t.st2.st[t.tin[i]] << endl; 
        assert(!(t.st1.st[t.tin[i]] > 0 && t.st2.st[t.tin[i]] > 0));
        if(!t.st1.st[t.tin[i]] && !t.st2.st[t.tin[i]]) {
            res[cur] = 'B';
        }
        else if(t.st1.st[t.tin[i]] && !t.st2.st[t.tin[i]]) {
            if(edg[cur][0] == i) {
                res[cur] = 'R';
            }
            else {
                res[cur] = 'L';
            }
        }
        else {
            if(edg[cur][0] != i) {
                res[cur] = 'R';
            }
            else {
                res[cur] = 'L';
            }
        }
    }
    for(int i = 0 ; i < m; i++) {

        cout << res[i];
    }
    cout << "\n";
    
}

signed main() {
    fastio();
    solve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 6 ms 9052 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 4 ms 9048 KB Output is correct
7 Correct 5 ms 9308 KB Output is correct
8 Correct 4 ms 9048 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 6 ms 9052 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 4 ms 9048 KB Output is correct
7 Correct 5 ms 9308 KB Output is correct
8 Correct 4 ms 9048 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct
11 Correct 27 ms 13916 KB Output is correct
12 Correct 31 ms 14516 KB Output is correct
13 Correct 35 ms 15184 KB Output is correct
14 Incorrect 55 ms 16468 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 6 ms 9052 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 4 ms 9048 KB Output is correct
7 Correct 5 ms 9308 KB Output is correct
8 Correct 4 ms 9048 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct
11 Correct 27 ms 13916 KB Output is correct
12 Correct 31 ms 14516 KB Output is correct
13 Correct 35 ms 15184 KB Output is correct
14 Incorrect 55 ms 16468 KB Output isn't correct
15 Halted 0 ms 0 KB -