제출 #696209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696209		Shayan86	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	66 ms	16424 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n';
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll N = 1e5 + 5;
const ll inf = 1e9 + 7;

ll n, m, q, sum[N], b[N], res[N], h[N];

bool mark[N];
vector<pair<int, pii>> adj[N];

void dfs(int v, pair<int, pii> ii = Mp(0, Mp(0, 0))){
    mark[v] = true;
    for(auto e: adj[v]){
        int u = e.F;
        if(!mark[u]){
            h[u] = h[v]+1;
            dfs(u, e);
            sum[v] += sum[u];
            b[v] += b[u];
        }
        else if(e.S.F != ii.S.F && h[v] > h[u]){
            b[v]++;
            b[u]--;
        }
    }
    if(b[v] > 0 || !sum[v]) return;

    if(true){
        bool up = sum[v] < 0;
        bool change = ii.S.S;
        if(up ^ change) res[ii.S.F] = 2;
        else res[ii.S.F] = 1;

        //cout << v << sep << up << sep << change << sep << (up ^ change) << endl;
    }
}

int main(){
    fast_io;

    cin >> n >> m;

    int u, v;
    for(int i = 1; i <= m; i++){
        cin >> u >> v;
        adj[u].pb(Mp(v, Mp(i, 0)));
        adj[v].pb(Mp(u, Mp(i, 1)));
    }

    cin >> q;

    for(int i = 1; i <= q; i++){
        cin >> u >> v;
        sum[u]++; sum[v]--;
    }

    for(int i = 1; i <= n; i++){
        if(!mark[i]){
            dfs(i);
        }
    }

    for(int i = 1; i <= m; i++){
        if(res[i] == 1)
            cout << 'L';
        else if(res[i] == 2)
            cout << 'R';
        else
            cout << 'B';
    }
    cout << endl;

}

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