제출 #287788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287788		thomas_li	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	10 ms	9984 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,disc[MM],ti,comp[MM],cid,diff[MM],low[MM];
char ans[MM];
vector<pi> adj[MM],adj1[MM];
bool vis[MM],vis1[MM];
vector<int> st;
void go(int u){
    low[u] = disc[u] = ++ti;
    st.eb(low[u]);
    for(auto&[v,i]:adj[u]){
        i >>= 1;
        if(!vis[i]){
            vis[i] = 1;
            if(!disc[v]) {go(v); low[u] = min(low[u],low[v]); }
            else low[u] = min(low[u],disc[v]);
        }
    }
    if(low[u] == disc[u]){
        cid++;
        int x;
        do{
            x = st.back(); st.pop_back();
            comp[x] = cid;
        } while(x != u);
    }

}

void dfs(int u, int p){
    vis1[u] = 1;
    for(auto&[v,i]:adj1[u]){
        if(v == p) continue;
        dfs(v,u);
        diff[u] += diff[v];
        if(diff[v]<0) ans[i>>1] = (i&1 ? 'R' : 'L');
        else if(diff[v]>0) ans[i>>1] = (!(i&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(!disc[i])
            go(i);
    }
    for(int i = 1; i <= n; i++)
        for(auto& [j,k] : adj[i])
            if(comp[i] != comp[j])
                adj1[comp[i]].pb({comp[j],k});
    cin >> p;
    for(int i = 0; i < p; i++){
        int a,b;
        cin >> a >> b;
        diff[comp[a]]++;
        diff[comp[b]]--;
    }
    //for(int i = 1; i <= cid; i++) cout << i << " " << diff[i] << "\n";
    for(int i = 1; i <= cid; i++)
        if(!vis1[i])
            dfs(i,0);
    cout << ans << "\n";
    //for(int i = 1; i <= n; i++) cout << i << " " << comp[i] << "\n";
}

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