Submission #1124828

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

oneway

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e5 + 15;
const int lg = 16;

int n, m, q;
pii edges[N];
vector<int> g[N];
int low[N], num[N], timerDFS;
int scc;
bool del[N];
stack<int> st;
int team[N];
int ans[N];
char luvna[] = {'B', 'R', 'L'};

void tarjan(int u, int pre_id){
    low[u] = num[u] = ++timerDFS;
    st.push(u);
    for(int id : g[u]) if(id != pre_id){
        int v = edges[id].fi ^ edges[id].se ^ u;
        if(del[v]) continue;
        if(num[v]) minimize(low[u], num[v]);
        else{
            tarjan(v,id);
            minimize(low[u], low[v]);
        }
    }
    if(low[u] == num[u]){
        int v;
        scc++;
        do{
            v = st.top(); st.pop();
            del[v] = true;
            team[v] = scc;
        }while(v != u);
    }
}

pii edgeSCC[N];
vector<int> adj[N];
int dp[N];

void dfsDP(int u, int pre_id){
    del[u] = true;
    for(int id : adj[u]) if(id != pre_id){
        int v = edgeSCC[id].fi ^ edgeSCC[id].se ^ u;
        dfsDP(v, id);
        dp[u] += dp[v];

        // u -> v -> v'
        if(dp[v] > 0) ans[id] = (u == edges[id].se) ? 1 : 2;
        else if(dp[v] < 0) ans[id] = (v == edges[id].se) ? 1 : 2;
    }
}

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

    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        edges[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 = edges[i].fi, v = edges[i].se;
        u = team[u], v = team[v];
        if(u == v) continue;
        edgeSCC[i] = {u,v};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }

    cin >> q;

    while(q--){
        int u, v; cin >> u >> v;
        u = team[u], v = team[v];
        dp[u]++, dp[v]--;
    }

    fill(del + 1, del + 1 + scc, 0);

    for(int i = 1; i <= scc; i++) if(!del[i]) dfsDP(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:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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