제출 #720551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720551		bane	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	7 ms	12012 KiB

oneway

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <string.h>
#include <bitset>
#include <numeric>
#include <utility>
#include <random>
#include <cassert>
#include<stack>
using namespace std;
//Arrays
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb(a,x) lower_bound(a.begin(), a.end(), x)
#define ub(a,x) upper_bound(a.begin(), a.end(), x)
#define mems(x) memset(x, 0, sizeof(x))
#define sz(a) ((int)a.size())
#define all(x) x.begin(), x.end()
#define fr first
#define sc second
//Input / Output
#define psn(x) cout<<x<<'\n'
#define pss(x) cout<<x<<' '
#define ps(x)cout<<x
#define debug(x) cout<<'['<<#x<<" = "<<x<<"]\n"
//Data Structures
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
//Order Statistic Tree
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;*/
int dfn[200001], low[200001];
vector<int>g[200001];
int pos=1;
int scc=0;
int comp[200001];
vector<int>nov[200001];
int dp[200001];
int dist[200001];
stack<int>inst;
void tarjan(int v, int p = -1){
        bool pp=0;
        inst.push(v);
        low[v]=dfn[v]=++pos;
        for(auto i:g[v]){
            if(i!=p||pp){
                if(!dfn[i]){
                    tarjan(i,v);
                    low[v]=min(low[v],low[i]);
                }
                else low[v]=min(low[v],dfn[i]);
            }
            else pp=1;
        }
        if(low[v]==dfn[v]){
            while(inst.top()!=v){
                comp[inst.top()]=scc;
                inst.pop();
            }
            comp[v]=scc++; inst.pop();
        }
}
void dfs(int v, int p = -1){
    for(int& x : nov[v]){
        if (x != p){
            dist[x] = dist[v] + 1;
            dfs(x, v);
            dp[v] += dp[x];
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dfn ,0 ,sizeof(dfn));
    memset(dp, 0, sizeof(dp));
    
    memset(dist, 0, sizeof(dist));
    int n, m;
    cin >> n >> m;
    vector<pii>edges;
    for(int i = 0; i < m ; i++){
        int a,b;
        cin >> a >> b;
        g[a].eb(b);
        g[b].eb(a);
        edges.eb(mp(a,b));
    }
    int p;
    cin >> p;
    //vector<pair<int,int>>edges;
    for (int i = 1; i<= n; i++){
        if(!dfn[i])tarjan(i);
    }
    for (int i = 1; i<=n; i++){
        for (int x : g[i]){
            if (comp[x] != comp[i]){
                nov[x].eb(i);
                nov[i].eb(x);
            }
        }
    }
    for (int i = 0; i < p; i++){
        int a,b;cin >> a >> b;
        dp[comp[a]]++;
        dp[comp[b]]--;
    }
    for (int i = 0; i < scc; i++){
        if(!dist[i])dfs(i);
    }
    for (auto i : edges){
        if (comp[i.fr] == comp[i.sc]){
            ps("B");continue;
        }
        i.fr = comp[i.fr];
        i.sc = comp[i.sc];
        if (dist[i.fr] > dist[i.sc]){
            if (dp[i.fr] >= 1){
                //i.sc is below i.fr
                //i.fr needs to go upwards
                cout<<'L';
            }
            if (dp[i.fr] == 0){
                cout<<'B';
            }
            if (dp[i.fr] < 0)cout<<'R';
        }else{
            if (dp[i.fr] >= 1){
                //i.fr is below i.sc
                //i.sc needs to go upwards
                cout<<'R';
            }
            if (dp[i.fr] == 0){
                cout<<'B';
            }
            if (dp[i.fr]< 0)cout<<'L';
        }
    }
    return 0;
}

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