oj.uz

Submission #563697

# Submission time Handle Problem Language Result Execution time Memory
563697 2022-05-18T02:40:40 Z hollwo_pelw One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3000 ms 5448 KB 
// ajjjhefz
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("oneway.inp", "r"))
		assert(freopen("oneway.inp", "r", stdin)), assert(freopen("oneway.out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 1e5 + 5;

int n, m, q, eu[N], ev[N], nnode, comp[N], vis[N];
vector<pair<int, int>> g[N], adj[N];

int tin[N], low[N], timer, st[N], top;

void tarjan(int u, int pi) {
    tin[u] = low[u] = ++ timer;
    st[++ top] = u;
    for (auto [v, i] : g[u]) if (i != pi) {
        if (tin[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        }
    }
    if (tin[u] == low[u]) {
        ++ nnode;
        while (top && st[top] != u)
            comp[st[top --]] = nnode;
        comp[st[top --]] = nnode;
    }
}

int h[N], par[17][N], ids[N], lif[17][N];
char res[N];

void pre_dfs(int u, int p, int pi) {
    h[u] = h[par[0][u] = p] + 1;
    for (int i = 1; i < 17; i++)
        par[i][u] = par[i - 1][par[i - 1][u]];
    ids[u] = pi, vis[u] = 1;
    for (auto [v, i] : adj[u]) if (v != p) {
        pre_dfs(v, u, i);
    }
}

void Hollwo_Pelw(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        g[eu[i]].emplace_back(ev[i], i);
        g[ev[i]].emplace_back(eu[i], i);
    }
    for (int i = 1; i <= n; i++)
        if (!tin[i]) tarjan(i, 0);
    
    for (int u = 1; u <= n; u++)
        for (auto [v, i] : g[u]) if (comp[u] != comp[v]) {
            adj[comp[u]].emplace_back(comp[v], i);
            adj[comp[v]].emplace_back(comp[u], i);
        }

    for (int i = 1; i <= nnode; i++) {
        if (!vis[i]) pre_dfs(i, 0, 0);
    }

    cin >> q;
    for (int u, v; q --; ) {
        cin >> u >> v;
        u = comp[u], v = comp[v];
        if (h[v] > h[u]) {
            for (int i = 17; i --; )
                if ((h[v] - h[u]) >> i & 1) {
                    lif[i][v] |= 1;
                    v = par[i][v];
                }
        }
        if (h[u] > h[v]) {
            for (int i = 17; i --; )
                if ((h[u] - h[v]) >> i & 1) {
                    lif[i][u] |= 2;
                    u = par[i][u];
                }
        }
        if (u == v) continue;
        for (int i = 17; i --; )
            if (par[i][u] ^ par[i][v]) {
                lif[i][u] |= 2;
                lif[i][v] |= 1;
                u = par[i][u];
                v = par[i][v];
            }
        lif[0][u] |= 2;
        lif[0][v] |= 1;
    }
    for (int i = 16; i; i --) {
        for (int u = 1; u <= nnode; u++) {
            lif[i - 1][u] |= lif[i][u];
            lif[i - 1][par[i - 1][u]] |= lif[i][u];
        }
    }

    fill(res + 1, res + m + 1, 'B');

    for (int u = 1; u <= nnode; u++) {
        if (lif[0][u] == 1) {
            if (comp[eu[ids[u]]] == u)
                res[ids[u]] = 'L';
            else
                res[ids[u]] = 'R';
        }
        if (lif[0][u] == 2) {
            if (comp[eu[ids[u]]] == u)
                res[ids[u]] = 'R';
            else
                res[ids[u]] = 'L';
        }
    }

    for (int i = 1; i <= m; i++)
        cout << res[i];
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 526 ms 5448 KB Output is correct
5 Execution timed out 3048 ms 5332 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 526 ms 5448 KB Output is correct
5 Execution timed out 3048 ms 5332 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 526 ms 5448 KB Output is correct
5 Execution timed out 3048 ms 5332 KB Time limit exceeded
6 Halted 0 ms 0 KB -