Submission #1106161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106161		PagodePaiva	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	522 ms	59388 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

vector <pair <int, int>> g[N];
vector <pair <int, int>> backedges[N];
int l[N], r[N];
int mark[N];
set <array <int, 3>> edges;
vector <array <int, 3>> arestas;
int tin[N], low[N], pai[N];
int tmm = 1;
char res[N];
map <pair <int,int>, int> look;
int aux[N];
int sz[N];

void dfs3(int v, int p){
    int val = -1;
    aux[v] = 1;
    sz[v] = l[v]-r[v];
    for(auto [x, i] : g[v]){
        if(x == p){
            val = i;
            look[{x, v}] = look[{v, x}] = i;
            continue; 
        }
        dfs3(x, v);
        sz[v] += sz[x];
    }
    if(val == -1) return;
    if(res[val] == 'B') return;
    if(sz[v] == 0){
        res[val] = 'B';
    }
    else if(sz[v] > 0){
        res[val] = 'U';
    }
    else{
        res[val] = 'D';
    }
}

void dfs2(int v, int p){
    pai[v] = p;
    tin[v] = tmm;
    tmm++;
    low[v] = tin[v];
    for(auto [x,i] : backedges[v]){
        if(tin[x] == 0) continue;
        low[v] = min(low[v], tin[x]);
    }
    for(auto [x,i] : g[v]){
        if(x == p) {
            look[{x, v}] = look[{v, x}] = i;
            continue;
        }
        dfs2(x,v);
        low[v] = min(low[v], low[x]);
    }
    tmm++;
    return;
}

void dfs(int v, int p){
    mark[v] = 1;
    for(auto [x, i] : g[v]){
        if(x == p) continue;
        if(mark[x] == 1) continue;
        edges.insert({v, x, i});
        edges.insert({x, v, i});
        dfs(x, v);
    }
    return;
}

map <pair <int, int>, int> buceta;

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        arestas.push_back({a, b, i});
        look[{a, b}] = i;
        look[{b, a}] = i;
        buceta[{a, b}] = 0;
        buceta[{b, a}] = 1;
    }
    int q;
    cin >> q;
    while(q--){
        int a, b;cin >> a >> b;
        l[a]++;
        r[b]++;
    }
    for(int i = 1;i <= n;i++){
        if(mark[i] == 0) dfs(i, i);
    }
    for(int i = 1;i <= n;i++) g[i].clear();
    for(auto [a, b, i] : edges){
        g[a].push_back({b, i});
    }
    for(auto [a, b, i] : arestas){
        if(edges.find({a, b, i}) != edges.end() or edges.find({b, a, i}) != edges.end()) continue;
        backedges[a].push_back({b, i});
        backedges[b].push_back({a, i});
        res[i] = 'B';
    }
    for(int i = 1;i <= n;i++){
        if(pai[i] == 0){
            dfs2(i, i);
        }
    }
    for(int i = 1;i <= n;i++){
        if(i == pai[i]) continue;
        if(low[i] <= tin[pai[i]]){
            int t = look[{i, pai[i]}];
            res[t] = 'B';
        } 
    }
    for(int i = 1;i <= n;i++){
        if(aux[i] == 0) dfs3(i, i);
    }
    for(int i = 1;i <= n;i++){
        if(i == pai[i]) continue;
        int val = look[{i, pai[i]}];
        if(res[val] == 'B') continue;   
        if(buceta[{i, pai[i]}] == 0){
            if(res[val] == 'U') res[val] = 'R';
            else res[val] = 'L';
        }
        else{
            if(res[val] == 'U') res[val] = 'L';
            else res[val] = 'R';
        }
    }
    //cout << m << '\n';
    for(int i = 0;i < m;i++){
        cout << res[i];
        if(res[i] != 'B' and res[i] != 'L' and res[i] != 'R') return 1;
    }
    cout << '\n';
}   

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