제출 #1197187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197187		HasanV11010238	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	136 ms	26380 KiB

oneway

#include <bits/stdc++.h>
#define ll long long
#define MAX 100000
#define INF 1000000000000000
#define mod 998244353
using namespace std;
vector<vector<vector<int>>> v;
vector<int> sbt, tin, low, vis;
string ans;
int ti = 0;
void dfs(int x, int p){
    vis[x] = 1;
    tin[x] = low[x] = ++ti;
    int ps = 0;
    for (auto el : v[x]){
        if (el[0] == p && ps == 0){
            ps = 1;
            continue;
        }
        if (vis[el[0]] == 1){
            low[x] = min(low[x], tin[el[0]]);
        }
        else{
            dfs(el[0], x);
            sbt[x] += sbt[el[0]];
            low[x] = min(low[x], low[el[0]]);
            if (low[el[0]] > tin[x]){
                if (sbt[el[0]] == 0) continue;
                int va = el[1] ^ (sbt[el[0]] > 0);
                if (va == 0) ans[el[2]] = 'R';
                else ans[el[2]] = 'L';
            }
        }
    }
}
int main(){
    int n, m, q, a, b;
    cin>>n>>m;
    v.assign(n + 1, vector<vector<int>>());
    ans.assign(m, 'B'), sbt.assign(n + 1, 0), tin.assign(n + 1, -1), low.assign(n + 1, -1), vis.assign(n + 1, 0);
    for (int i = 0; i < m; i++){
        cin>>a>>b;
        v[a].push_back({b, 0, i});
        v[b].push_back({a, 1, i});
    }
    cin>>q;
    for (int i = 0; i < q; i++){
        cin>>a>>b;
        sbt[a]++, sbt[b]--;
    }
    for (int i = 1; i <= n; i++){
        if (vis[i] == 0) dfs(i, 0);
    }
    for (int i = 0; i < m; i++){
        cout<<ans[i];
    }
}

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