Submission #1027374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027374		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	68 ms	35156 KiB

oneway

// THIS IS ACTUALLY PROBLEM A
// CEOI 2017 - One-Way Streets
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e5+5, inf=1e18;

ll n,m,pp,p[20][maxn],depth[maxn],num[maxn],low[maxn],tail[maxn],timer,par[maxn],par_[maxn],pf[maxn];
char ans[maxn];
vector<pair<ll,ll>> G[maxn];

void dfs(ll u){
    num[u] = timer;
    low[u] = timer++;
    for(auto edge: G[u]){
        ll c = edge.first, idx = edge.second;
        ans[abs(idx)] = 'B';
        if(c == u || idx == -par_[u]) continue;
        if(!num[c]){
            par_[c] = idx;
            dfs(c);
            low[u] = min(low[u], low[c]);
        }else{
            low[u] = min(low[u], num[c]);
        }
    }
    tail[u] = timer - 1;
}

void dfs2(ll u, ll pp){
    par[u] = pp;
    p[0][u] = pp;
    for(ll i=1;i<=19;i++){
        ll lift = p[i-1][u];
        if(lift == -1) p[i][u] = -1;
        else p[i][u] = p[i-1][lift];
    }
    for(auto edge: G[u]){
        ll c = edge.first, idx = edge.second;
        if(par_[c] == idx) {
            depth[c] = depth[u] + 1;
            dfs2(c, u);
        }
    }
}

ll solve(ll u, ll up){
    if(up == 0){
        return u;
    }
    ll msb = __lg(up);
    ll lift = p[msb][u];
    if(lift == -1) return -1;
    return solve(lift, up - (1 << msb));
}

ll LCA(ll u, ll v){
    if(depth[u] > depth[v]) swap(u, v);
    ll oru = u, orv = v;
    v = solve(v, depth[v] - depth[u]);
    for(ll i=19;i>=0;i--){
        if(p[i][u] != p[i][v]){
            u = p[i][u];
            v = p[i][v];
        }
    }
    if(u != v) {u = p[0][u]; v = p[0][v];}
    return u;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m;
    f1(i,m){
        ll u, v; cin >> u >> v;
        G[u].push_back({v, i});
        G[v].push_back({u, -i});
    }
    timer = 1;
    f1(i,n) if(!num[i]) dfs(i);
    dfs2(1, -1);
    // f1(i,n) cout << num[i] << ' ' << low[i] << '\n';
    cin >> pp;
    while(pp--){
        ll x, y; cin >> x >> y;
        pf[num[x]]++;
        pf[num[y]]--;
    }
    f1(i, n) pf[i] += pf[i-1];
    for(ll u=2;u<=n;u++){
        if(low[u] == num[u]){
            // u -> par[u] is a bridge
            ll curd = par_[u] / abs(par_[u]), idx = abs(par_[u]);
            if(pf[tail[u]] - pf[num[u] - 1] > 0){
                // exist
                ans[idx] = ((curd) == 1 ? 'L' : 'R');
            }else if(pf[tail[u]] - pf[num[u] - 1] < 0){
                ans[idx] = ((-curd) == 1 ? 'L' : 'R');
            }
        }
    }
    f1(i,m) cout << ans[i];
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

oneway.cpp: In function 'long long int LCA(long long int, long long int)':
oneway.cpp:63:8: warning: unused variable 'oru' [-Wunused-variable]
   63 |     ll oru = u, orv = v;
      |        ^~~
oneway.cpp:63:17: warning: unused variable 'orv' [-Wunused-variable]
   63 |     ll oru = u, orv = v;
      |                 ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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