oj.uz

Submission #1027374

# Submission time Handle Problem Language Result Execution time Memory
1027374 2024-07-19T05:19:51 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 68 ms 35156 KB 
// 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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19084 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 3 ms 15100 KB Output is correct
8 Correct 2 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19084 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 3 ms 15100 KB Output is correct
8 Correct 2 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 37 ms 25428 KB Output is correct
12 Correct 56 ms 25540 KB Output is correct
13 Correct 45 ms 28760 KB Output is correct
14 Correct 46 ms 30812 KB Output is correct
15 Correct 50 ms 31420 KB Output is correct
16 Correct 42 ms 30292 KB Output is correct
17 Correct 45 ms 31580 KB Output is correct
18 Correct 40 ms 30292 KB Output is correct
19 Correct 47 ms 32340 KB Output is correct
20 Correct 36 ms 27484 KB Output is correct
21 Correct 35 ms 28120 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19084 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 3 ms 15100 KB Output is correct
8 Correct 2 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 37 ms 25428 KB Output is correct
12 Correct 56 ms 25540 KB Output is correct
13 Correct 45 ms 28760 KB Output is correct
14 Correct 46 ms 30812 KB Output is correct
15 Correct 50 ms 31420 KB Output is correct
16 Correct 42 ms 30292 KB Output is correct
17 Correct 45 ms 31580 KB Output is correct
18 Correct 40 ms 30292 KB Output is correct
19 Correct 47 ms 32340 KB Output is correct
20 Correct 36 ms 27484 KB Output is correct
21 Correct 35 ms 28120 KB Output is correct
22 Correct 68 ms 32596 KB Output is correct
23 Correct 55 ms 31312 KB Output is correct
24 Correct 58 ms 31328 KB Output is correct
25 Correct 60 ms 35156 KB Output is correct
26 Correct 54 ms 32336 KB Output is correct
27 Correct 59 ms 31568 KB Output is correct
28 Correct 28 ms 24404 KB Output is correct
29 Correct 46 ms 28324 KB Output is correct
30 Correct 45 ms 29268 KB Output is correct
31 Correct 48 ms 29520 KB Output is correct
32 Correct 53 ms 30804 KB Output is correct