Submission #287794

#	Time	Username	Problem	Language	Result	Execution time	Memory
287794		thomas_li	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	119 ms	21464 KiB

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int INF = 0x3f3f3f3f; constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f;
#define db(x) { cerr << #x << " = " << x << endl; }
template <typename T> void _dbarr(T* a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
template <typename T> void _dbarr(vector<T> a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
#define dbarr(x, n) {cerr << #x << ": "; _dbarr((x),(n));}
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define fs first
#define sn second
const int MM = 1e5+5;
int n,m,p,comp[MM],diff[MM],disc[MM],x,ti,cid;
vector<pi> adj[MM],adj1[MM];
bool vis[MM], vis1[MM];
char ans[MM];
vector<int> st;
int go(int u){
    int low = disc[u]= ++ti;
    st.eb(u);
    for(auto[v,w] : adj[u]){
        w >>= 1;
        if(!vis[w]){
            vis[w] = 1;
            low = min(low,disc[v]?:go(v));
        }
    }
    if(low == disc[u]){
        cid++;
        do{
            x = st.back(), st.pop_back(); comp[x] = cid;
        }while(x != u);
    }
    return low;
}

void dfs(int u, int pa){
    vis1[u] = 1;
    for(auto[v,w] : adj1[u]){
        if(v == pa) continue;
        dfs(v,u); diff[u]+=diff[v];
        if(diff[v] < 0) ans[w>>1] = (w&1 ? 'L' : 'R');
        else if(diff[v] > 0) ans[w>>1] = (!(w&1) ? 'L' : 'R');
    }
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	//freopen("in.txt","r", stdin);
    cin >> n >> m;
    for(int i = 0, j = 0, u = 0, v = 0; i < m; i++){
        cin >> u >> v; ans[i] = 'B';
        adj[u].push_back({v,j++}); adj[v].push_back({u,j++});
    }
    for(int i = 1; i <= n; i++) if(!disc[i]) go(i);
    cin >> p;
    for(int i = 1; i <= p; i++){
        int u,v;
        cin >> u >> v;
        diff[comp[u]]++; diff[comp[v]]--;
    }
    for(int u = 1; u <= n; u++) for(auto&[v,w] : adj[u])
        if(comp[u] != comp[v])
            adj1[comp[u]].push_back({comp[v],w});
    for(int i = 1; i <= cid; i++) if(!vis1[i])
        dfs(i,-1);

    cout << ans << "\n";
}

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