Submission #1368815

#TimeUsernameProblemLanguageResultExecution timeMemory
1368815dhuyyyyOne-Way Streets (CEOI17_oneway)C++20
100 / 100
144 ms36468 KiB
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(s) s.begin(),s.end()
#define sz(s) (int)s.size()

using namespace std;

using ll = long long;
using ii = pair<int,int>;
using aa = array<int,3>;

const int N = 1e5+5;
const int blocks = 224;
const ll INF = 1e18;
const int MOD = 1e9+7;

int n, m, u, v, k, U, V, scc = 0, ans = 0, timer = 0;

int a[N], c[N], low[N], num[N], pre[N];

vector <int> adj[N], g[N];

vector <ii> edges;

stack<int> st;

map<ii,int> mp;

set <ii> s;

void dfs(int u,int p){
    low[u] = num[u] = ++timer;
    bool ok = 0;
    st.push(u);
    for (int it : adj[u]){
        if (it == p && !ok){
            ok = 1;
            continue;
        }
        if (!num[it]){
            dfs(it,u);
            low[u] = min(low[u],low[it]);
        } else low[u] = min(low[u],num[it]);
    }
    if (low[u] == num[u]){
        int v = -1;
        ++scc;
        while (v != u){
            v = st.top();
            st.pop();
            c[v] = scc;
        }
    }
}

void DFS(int u,int p){
    num[u] = 1;
    for (int it : g[u]){
        if (it == p) continue;
        DFS(it,u);
        pre[u] += pre[it];
    }
    if (pre[u] < 0) mp[{p,u}] = 1; // đi từ p tới u
    else if (pre[u] > 0) mp[{p,u}] = 2; // đi từ u tới p
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    #define name "PHANLUONG"
    if (fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u,v});
    }
    for (int i = 1; i <= n; i++){
        if (!num[i]) dfs(i,0);
    }
    for (int i = 1; i <= scc; i++) num[i] = 0;
    for (ii it : edges){
        tie(u,v) = it;
        U = c[u];
        V = c[v];
        if (U > V) swap(U,V);
        if (U != V && s.find({U,V}) == s.end()){
            g[U].push_back(V);
            g[V].push_back(U);
            s.insert({U,V});
        }
    }
    cin >> k;
    for (int i = 1; i <= k; i++){
        cin >> u >> v;
        pre[c[u]]++;
        pre[c[v]]--;
    }
    for (int i = 1; i <= scc; i++){
        if (!num[i]) DFS(i,0);
    }
    for (ii it : edges){
        tie(u,v) = it;
        U = c[u];
        V = c[v];
        if (U == V) cout << 'B';
        else{
            if (mp.count({U,V}) == 0 && mp.count({V,U}) == 0) cout << 'B';
            else{
                if (mp.count({U,V})){
                    if (mp[{U,V}] == 1) cout << 'R';
                    else cout << 'L';
                } else{
                    if (mp[{V,U}] == 1) cout << 'L';
                    else cout << 'R';
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...