oj.uz

Submission #849067

# Submission time Handle Problem Language Result Execution time Memory
849067 2023-09-14T04:05:11 Z omega One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3000 ms 4696 KB 
/* * * * * * * * * * * * * * * * *
 *	author: enmendurana
 *	created: 09-14-2023
 * * * * * * * * * * * * * * * * */

#include <bits/stdc++.h>

using namespace std;

struct buffer : streambuf {
    int overflow(int x) {
        return x;
    }
};

static buffer null_buffer;
static ostream null_stream(&null_buffer);

void local() {
	#if defined(LOCAL_FLAG)
		freopen("/home/omega/Documents/input.in", "r", stdin);
		freopen("/home/omega/Documents/output.out", "w", stdout);
		freopen("/home/omega/Documents/error.err", "w", stderr);
        #define debug cerr
	#else
        #define debug null_stream
	#endif
}

#define ff first
#define ss second
#define pb emplace_back
#define pob pop_back
#define pf emplace_front
#define pof pop_front
#define endl '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef tuple<ll,ll,ll> tlll;

const ll mod = ll(1e9 + 7);
const int N = 10'000;
const int maxn = int(1e5)+10;
const int lg = 21;
const double eps = double(1e-9);

/* ALGORITHM */

vector<vector<int>> g;

int edge[maxn], smer[maxn];
int d[maxn], low[maxn], timer = 0;

int p[maxn], cycle[maxn];
int aux[maxn], sz[maxn];

stack<int> st;

int idx[maxn], bit[maxn];

int t[4*maxn];

int tarjan_dfs(int prev, int v) {
    d[v] = low[v] = ++timer;
    p[v] = prev;

    sz[v] = 1;
    st.emplace(v);

    for(int i : g[v]) {
        int u = edge[i] - v;
        if(!d[u]) {
            d[u] = d[v] + 1;
            sz[v] += tarjan_dfs(v,u);

            low[v] = min(low[v], low[u]);
        } else if(u != prev) {
            low[v] = min(low[v], d[u]);
        }
    }

    if(d[v] == low[v]) {
        for(int u = 0; u != v;) {
            u = st.top(); st.pop();
            cycle[u] = v;
        }
    }

    return sz[v];
}

void hld(int r, int v) {
    priority_queue<ii> pq;
    aux[v] = r;

    idx[v] = timer++;

    for(int i : g[v]) {
        int u = edge[i] - v;
        if(p[u] == v) {
            pq.emplace(sz[u], u);
        }
    }

    if(!pq.empty()) {
        auto [w,u] = pq.top(); pq.pop();
        hld(r,u);
    }

    while(!pq.empty()) {
        auto [w,u] = pq.top(); pq.pop();
        hld(u,u);
    }
}

void update(int v, int l, int r, int lx, int rx, int x) {
    if(lx <= l && r <= rx) t[v] = x;
    else if(r <= lx || rx <= l) return;
    else {
        int mid = (l+r)>>1;
        update(2*v,l,mid,lx,rx, x);
        update(2*v+1,mid,r,lx,rx, x);
    }
}

void lca(int v, int u) {
    while(aux[v] != aux[u]) {
        if(d[aux[v]] < d[aux[u]]) {
            update(1,0,2*timer,idx[aux[u]],idx[u]+1,-1);
            u = p[aux[u]];
        } else {
            update(1,0,2*timer,idx[aux[v]],idx[v]+1,1);
            v = p[aux[v]];
        }
    }
    if(d[v] < d[u]) update(1,0,2*timer,idx[v]+1,idx[u]+1,-1);
    if(d[v] > d[u]) update(1,0,2*timer,idx[u]+1,idx[v]+1,1);
}

int mode[maxn];

void build(int v, int l, int r) {
    if(r-l==1) {
        if(l < timer) mode[l] = t[v];
    } else {
        if(t[v] != 0) t[2*v] = t[2*v+1] = t[v];
        int mid = (l+r)>>1;
        build(2*v,l,mid);
        build(2*v+1,mid,r);
    }
}

void solve() {

    int n, m; cin >> n >> m;

    g.resize(n+1);

    for(int v, u, i = 0; i < m; i++) {
        cin >> v >> u; 
        edge[i] = v + u;
        smer[i] = (v < u);
        g[v].pb(i);
        g[u].pb(i);
    }

    for(int v = 1; v <= n; v++) {
        if(!d[v]) tarjan_dfs(v,v);
    }
    timer = 0;

    for(int v = 1; v <= n; v++) {
        if(v==p[v]) hld(v,v);
    }

    int k; cin >> k;

    for(int v, u; k--;) {
        cin >> v >> u; lca(v,u);
    }

    build(1,0,2*timer);
    string ans; ans.resize(m);

    for(int v = 1; v <= n; v++) {
        for(int i : g[v]) {
            int u = edge[i] - v;
            int op = mode[idx[u]];
            if(cycle[v] == cycle[u]) {
                ans[i] = 'B'; continue;
            }

            if(p[u] == v) {
                if(op==1) {
                    if((u < v) ^ smer[i]) op = -1;
                    else op = 1;
                } else if(op==-1) {
                    if((v < u) ^ smer[i]) op = -1;
                    else op = 1;
                }

                if(op==1) ans[i] = 'R';
                if(op==-1) ans[i] = 'L';
                if(op==0) ans[i] = 'B';
            }
        }
    }

    cout << ans << "\n";

}

signed main() {
	local();
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	return 0;
}

// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Execution timed out 3037 ms 2396 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Execution timed out 3037 ms 2396 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Execution timed out 3037 ms 2396 KB Time limit exceeded
7 Halted 0 ms 0 KB -