Submission #1027475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027475		khanhtb	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	63 ms	25028 KiB

oneway

#include <bits/stdc++.h>
#define ll int
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 1e5 + 8;
ll num[N],low[N],tdfs,m,n,q;
bool vst[N];
vpll adj[N];
bool bridge[N];
vpll edge = {{0,0}};
void dfs_bridge(ll u, ll p){
    num[u] = low[u] = ++tdfs;
    for(pll ed:adj[u]){
        ll v = ed.fi, id = ed.se;
        if(v == p) continue;
        if(!num[v]){
            dfs_bridge(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] == num[v]){
                bridge[id] = 1;
            }
        }
        else low[u] = min(low[u],num[v]);
    }
}
ll cc[N],cntcc;
void dfs_component(ll u){
    cc[u] = cntcc;
    vst[u] = 1;
    for(pll ed:adj[u]){
        ll v = ed.fi, id = ed.se;
        if(bridge[id]) continue;
        if(vst[v]) continue;
        dfs_component(v);
    }
}
struct node{
    ll v,id,x,y;
};
vector<node> g[N];
void build(){
    for(ll i = 1; i <= n; i++) if(!num[i]) tdfs = 0, dfs_bridge(i,i);
    for(ll i = 1; i <= n; i++) if(!vst[i]) cntcc++,dfs_component(i);
    for(ll i = 1; i <= m; i++){
        ll u = edge[i].fi, v = edge[i].se;
        if(bridge[i]){
            g[cc[u]].pb({cc[v],i,u,v});
            g[cc[v]].pb({cc[u],i,v,u});
        }
    }
}
ll dp[N];
pll ans[N];
void direct(ll u, ll p){
    vst[u] = 1;
    for(node v:g[u]){
        if(v.v == p || vst[v.v]) continue;
        v.x = u, v.y = v.v;
        direct(v.v,u);
    }
}
void dfs(ll u, ll p) {
    vst[u] = 1;
    for(node v:g[u]){
        if(v.v == p || vst[v.v]) continue;
        dfs(v.v, u);
        dp[u] += dp[v.v];
        if(dp[v.v] > 0) ans[v.id] = {v.y, v.x};
        if(dp[v.v] < 0) ans[v.id] = {v.x, v.y};
    }
}
void solve(){
    cin >> n >> m;
    for(ll i = 1; i <= m; i++){
        ans[i] = {-1,-1};
        ll u,v;cin >> u >> v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        edge.pb({u,v});
    }
    build();
    fill(vst,vst+n+1,0);
    for(ll i = 1; i <= n; i++) if(!vst[i]) direct(i,i); 
    cin >> q;
    while(q--){
        ll u,v;cin >> u >> v;
        dp[cc[u]]++;
        dp[cc[v]]--;
    }
    fill(vst,vst+n+1,0);
    for(ll i = 1; i <= n; i++) if(!vst[i]) dfs(i,i);
    for(ll i = 1; i <= m; i++) {
        if(ans[i].fi < 0 || !bridge[i]) cout << "B";
        else cout << (ans[i] == edge[i] ? "R" : "L");
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++){
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

oneway.cpp:16:16: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   16 | const ll inf = 2e18;
      |                ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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