Submission #1221835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221835		vanea	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3095 ms	4928 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e5+10;

int id[mxN], low[mxN], timer = 0, p[mxN], dep[mxN], ans[mxN];
vector<array<int, 3>> adj[mxN], adj1[mxN];
stack<int> s;
array<int, 3> par[mxN];

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int a, int b) {
    a = get(a); b = get(b);
    if(a == b) return ;
    p[a] += p[b];
    p[b] = a;
}

int dfs(int node, int p, int idx = -1) {
    id[node] = low[node] = ++timer;
    bool multiple_edges = false;
    s.push(node);
    for(auto [it, idx, flag] : adj[node]) {
        if(it == p) {
            if(!multiple_edges) {
                multiple_edges = true;
                continue;
            }
        }
        if(!id[it]) {
            dfs(it, node, idx);
            low[node] = min(low[node], low[it]);
        }
        else {
            low[node] = min(low[node], id[it]);
        }
    }
    if(low[node] == id[node]) {
        while(s.top() != node) {
            uni(node, s.top());
            s.pop();
        }
        s.pop();
    }
}

void dfs1(int node, int p, int idx = 0, int flag = 0) {
    if(p != 0) par[node] = {p, idx, -flag};
    for(auto [it, idx, flag] : adj1[node]) {
        if(it == p) continue;
        dep[it] = dep[node]+1;
        dfs1(it, node, idx, flag);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i, 1});
        adj[b].push_back({a, i, -1});
    }
    for(int i = 1; i <= n; i++) {
        p[i] = -1;
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) {
        int par = get(i);
        for(auto [it, idx, flag] : adj[i]) {
            int now = get(it);
            if(now != par) {
                adj1[now].push_back({par, idx, -flag});
                adj1[par].push_back({now, idx, flag});
            }
        }
    }
    //dfs1(get(1), 0);
    int p;
    cin >> p;
    while(p--) {
        int a, b;
        cin >> a >> b;
        int p_a = get(a), p_b = get(b);
        /*if(p_a != p_b) {
            while(dep[p_a] > dep[p_b]) {
                if(p_a == 0) break;
                auto now = par[p_a];
                if(now[2] == -1) ans[now[1]] = 1;
                else ans[now[1]] = 2;
                uni(p_a, now[0]);
                p_a = now[0];
            }
            while(dep[p_a] < dep[p_b]) {
                if(p_b == 0) break;
                auto now = par[p_b];
                if(now[2] == 1) ans[now[1]] = 2;
                else ans[now[1]] = 1;
                uni(p_b, now[0]);
                p_b = now[0];
            }
            while(p_a != p_b) {
                if(p_a == 0 || p_b == 0) break;
                auto now1 = par[p_a], now2 = par[p_b];
                if(now1[2] == -1) ans[now1[1]] = 1;
                else ans[now1[1]] = 2;
                if(now2[2] == -1) ans[now2[1]] = 2;
                else ans[now2[1]] = 1;
                uni(p_a, now1[0]); uni(p_b, now2[0]);
                p_a = now1[0]; p_b = now2[0];
            }
        }*/
    }
    for(int i = 0; i < m; i++) {
        if(ans[i] == 0) cout << 'B';
        else if(ans[i] == 1) cout << 'L';
        else cout << 'R';
    }
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int dfs(int, int, int)':
oneway.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
   49 | }
      | ^

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