Submission #249071

#	Time	Username	Problem	Language	Result	Execution time	Memory
249071		Sorting	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	2688 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;

int n, m, p;
vector<pair<int, int>> adjacent[k_N];
pair<int, int> edges[k_N];

bool used[k_N];
int depth[k_N];
char ans[k_N];

int cycle(int node, int p_idx){
    used[node] = true;

    int ret = node;
    for(auto [to, idx]: adjacent[node]){
        if(idx == p_idx)
            continue;
        if(used[to]){
            ans[idx] = 'B';
            if(depth[to] < depth[ret]) ret = to;
        }
        else{
            depth[to] = depth[node] + 1;
            int x = cycle(to, idx);
            if(x != to) ans[idx] = 'B';
            if(depth[x] < depth[ret]) ret = x;
        }
    }

    return ret;
}

bool dfs(int start, int end){
    used[start] = true;
    if(start == end)
        return true;

    for(auto [to, idx]: adjacent[start]){
        if(used[to])
            continue;
        if(dfs(to, end)){
            if(ans[idx] != 'B'){
                if(edges[idx].first == start) ans[idx] = 'R';
                else ans[idx] = 'L';
            }
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;

        adjacent[u].push_back({v, i});
        adjacent[v].push_back({u, i});
        ans[i] = 'U';
        edges[i] = {u, v};
    }

    for(int i = 1; i <= n; ++i){
        if(!used[i]){
            depth[i] = 0;
            cycle(i, -1);
        }
    }

    cin >> p;
    for(int i = 0; i < p; ++i){
        int u, v;
        cin >> u >> v;

        for(int j = 1; j <= n; ++j)
            used[j] = false;
        dfs(u, v);
    }

    for(int i = 0; i < m; ++i)
        cout << ans[i];
    cout << "\n";
}

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