Submission #1027283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027283		khanhphucscratch	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	7000 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
set<pair<int, int>> edges;
map<pair<int, int>, int> f;
map<pair<int, int>, pair<int, int>> edge_tree_to_graph;
vector<pair<int, int>> bridges;
vector<int> ad[100005], ad2[100005];
int low[100005], num[100005], c[100005], dp[100005], ans[100005], dfsc = 0, color = 1;
//0 = B; 1 = L; 2 = R;
bool visited[100005];
inline pair<int, int> edgeCorrection(pair<int, int> x)
{
    if(edges.count(x) == 0) swap(x.first, x.second);
    return x;
}
void dfs(int u, int par)
{
    low[u] = num[u] = ++dfsc;
    bool avoidpar = 1;
    for(int v : ad[u]){
        if(v != par || avoidpar == 0){
            if(num[v] > 0) low[u] = min(low[u], num[v]);
            else{
                dfs(v, u);
                low[u] = min(low[u], low[v]);
            }
        }
        else avoidpar = 0;
    }
}
void dfscolor(int u)
{
    visited[u] = 1; c[u] = color;
    for(int v : ad[u]) if(visited[v] == 0){
        if(low[v] == num[v]){
            color++;
            bridges.push_back(edgeCorrection({u, v}));
        }
        dfscolor(v);
    }
}
void dfsdirect(int u)
{
    visited[u] = 1;
    for(int v : ad2[u]) if(visited[v] == 0){
        dfsdirect(v); dp[u] += dp[v];
        if(dp[v] != 0){
            pair<int, int> thisedge = edge_tree_to_graph[{u, v}];
            if(dp[v] > 0){
                if(c[thisedge.first] == u) ans[f[thisedge]] = 1;
                else ans[f[thisedge]] = 2;
            }
            else{
                if(c[thisedge.first] == u) ans[f[thisedge]] = 2;
                else ans[f[thisedge]] = 1;
            }
        }
    }
    //cout<<u<<" "<<dp[u]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin>>u>>v;
        ad[u].push_back(v);
        ad[v].push_back(u);
        edges.insert({u, v});
        f[{u, v}] = i;
    }
    for(int i = 1; i <= n; i++) if(num[i] == 0){
        dfs(i, -1);
        dfscolor(i);
    }
    for(pair<int, int> i : bridges){
        ad2[c[i.first]].push_back(c[i.second]);
        ad2[c[i.second]].push_back(c[i.first]);
        edge_tree_to_graph[{c[i.first], c[i.second]}] = i;
        edge_tree_to_graph[{c[i.second], c[i.first]}] = i;
    }
    int p; cin>>p;
    for(int i = 1; i <= p; i++){
        int u, v;
        cin>>u>>v;
        dp[c[u]]++; dp[c[v]]--;
    }
    //cout<<"A"<<color<<" "<<bridges.size()<<endl;
    memset(visited, 0, sizeof(visited));
    for(int i = 1; i <= color; i++) if(visited[i] == 0){
        dfsdirect(i);
    }
    for(int i = 1; i <= m; i++){
        if(ans[i] == 0) cout<<"B";
        else if(ans[i] == 1) cout<<"L";
        else cout<<"R";
    }
}

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