Submission #287790

#	Time	Username	Problem	Language	Result	Execution time	Memory
287790		thomas_li	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	4 ms	5120 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,scc,id[MM],val[MM],dfn[MM],low[MM],x,ti;
vector<pi> adj[MM],adj1[MM]; char ans[MM]; bool vis[MM], vis1[MM];
vector<int> st;
void go(int u){
    low[u] = dfn[u] = ++ti; st.eb(u);
    for(auto&[v,w]:adj[u]){
        w /= 2;
        if(!vis[w]){
            vis[w] = 1;
            if(!dfn[v]) {go(v); low[u] = min(low[u],low[v]);}
            else low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        scc++;
        do{
            x = st.back(); st.pop_back();
            id[x] = scc;
        } while(x != u);
    }
}

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

int main(){
	cin.tie(0)->sync_with_stdio(0);
	//freopen("in.txt","r", stdin);
    cin >> n >> m;
    for(int i = 0,j=0; i < m; i++){
        int a,b;
        cin >> a >> b; ans[i] = 'B';
        adj[a].pb({b,j++}); adj[b].pb({a,j++});
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) go(i);

    for(int i = 1; i <= n; i++)
        for(auto&[j,w] : adj[i])
            if(id[i] != id[j])
                adj1[id[i]].pb({id[j],w});
    cin >> p;
    for(int i = 0; i < p; i++){
        int a,b;
        cin >> a >> b;
        val[id[a]]++; val[id[b]]--;
    }
    for(int i = 1; i <= scc; i++)
        if(!vis1[i]) dfs(i,-1);

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

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