Submission #1124829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124829		luvna	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	73 ms	24904 KiB

oneway

#include<bits/stdc++.h>

#define endl "\n"

using namespace std;

const int N = 2e5 + 15;

int n, m, q;
//save id
vector<int> g[N];
//save id scc
vector<int> adj[N];
pair<int,int> orGraph[N];
pair<int,int> orSccGraph[N];
int low[N], num[N], timerDFS;
bool del[N];
stack<int> st;
int team[N];
int scc;
int ans[N];
int f[N];
char luvna[] = {'B', 'R', 'L'};

void tarjan(int u, int pre_id){
    low[u] = num[u] = ++timerDFS;
    st.push(u);
    for(int cur_id : g[u]) if(cur_id != pre_id){
        int v = u ^ orGraph[cur_id].first ^ orGraph[cur_id].second;
        if(del[v]) continue;
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            tarjan(v, cur_id);
            low[u] = min(low[u], low[v]);
        }
    }
    if(low[u] == num[u]){
        scc++;
        int v;
        do{
            v = st.top(); st.pop();
            del[v] = true;
            team[v] = scc;
        }while(v != u);
    }
}

void dfs(int u, int pre_id){
    del[u] = true;

    for(int cur_id : adj[u]) if(cur_id != pre_id){
        int v = u ^ orSccGraph[cur_id].first ^ orSccGraph[cur_id].second;
        dfs(v, cur_id);
        f[u] += f[v];
        if(f[v] == 0) ans[cur_id] = 0;
        else if(f[v] > 0) ans[cur_id] = (u == orSccGraph[cur_id].second) ? 1 : 2;
        else ans[cur_id] = (v == orSccGraph[cur_id].second) ? 1 : 2;
    }
}

void solve(){
    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        orGraph[i] = {u,v};
        g[u].push_back(i);
        g[v].push_back(i);
    }

    for(int i = 1; i <= n; i++) if(!num[i]) tarjan(i, -1);

    for(int i = 1; i <= m; i++){
        int u = orGraph[i].first, v = orGraph[i].second;
        u = team[u], v = team[v];
        orSccGraph[i] = {u,v};
        if(u != v){
            adj[u].push_back(i);
            adj[v].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++) del[i] = false;

    cin >> q;

    for(int i = 1; i <= q; i++){
        int u, v; cin >> u >> v;
        u = team[u], v = team[v];
        f[u]++, f[v]--;
    }

    for(int i = 1; i <= scc; i++) if(!del[i]) dfs(i, -1);

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

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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