oj.uz

Submission #761056

# Submission time Handle Problem Language Result Execution time Memory
761056 2023-06-19T06:59:56 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 315 ms 31752 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 1e5 + 5; 

int n, m, q; 
int U[N], V[N], col, color[N], direction[N]; 
bool is_bridge[N], vis[N]; 
int tin[N], tout[N], tim, low[N], up[N][17], pa[N], sz[N]; 
int st[4*N]; 
int head[N], co, chain[N];
int p[N], ID;  

vector <int> adj[N], tree[N], curr;   

void dfs(int u, int f){
    tin[u] = low[u] = ++tim; 
    up[u][0] = pa[u] = f; 
    sz[u] = 1; 
    f(i,1,17) up[u][i] = up[up[u][i-1]][i-1];
    curr.push_back(u); 

    int r = 0;  
    for(int v: adj[u]){
        if(v == f) {r++; continue; } 
        if(tin[v] == 0){
            tree[u].push_back(v), tree[v].push_back(u); 
            dfs(v, u); 
            sz[u] += sz[v]; 
            low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], tin[v]); 
    }
    tout[u] = ++tim; 
    if(low[u] == tin[u] and r <= 1) {
        col++; 
        while(!curr.empty()){
            int w = curr.back();
            color[w] = col; 
            curr.pop_back(); 
            if(w == u) break; 
        }
        if(f != 0) 
            is_bridge[u] = 1;
    }
}
bool is(int u, int v){
    return tin[u] <= tin[v] and tout[u] >= tout[v]; 
}
int lca(int u, int v){
    if(is(u, v)) return u; 
    if(is(v, u)) return v; 
    fa(i,16,0){
        if(up[u][i] == 0 or is(up[u][i], v)) continue; 
        u = up[u][i]; 
    }
    return up[u][0]; 
}
int node(int u, int v){
    fa(i,16,0){
        if(up[u][i] == 0 or is(up[u][i], v)) continue; 
        u = up[u][i]; 
    }
    return u; 
}
void HLD(int u, int f){
    chain[u] = co; 
    p[u] = ++ID; 
    vis[u] = 1; 

    int Bchild = -1, size = 0; 
    for(int v: tree[u]){
        if(v == f) continue; 
        if(sz[v] > size){
            size = sz[v]; 
            Bchild = v; 
        }
    }
    if(Bchild != -1){
        HLD(Bchild, u); 
    }
    for(int v: tree[u]){
        if(v != f and v != Bchild){
            head[++co] = v; 
            HLD(v, u); 
        }
    }
}
void Upd(int id, int l, int r, int x, int y, int val){
    if(r < x or y < l) return; 
    if(x <= l and r <= y){
        st[id] = val;
        return; 
    }
    int m = (l+r)>>1; 
    Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val); 
}
int Query(int id, int l, int r, int x){
    if(r < x or x < l) return 0; 
    if(st[id] != 0 or l == r) return st[id]; 
    int m = (l+r)>>1; 
    if(x <= m) return Query(id<<1, l, m, x); 
    return Query(id<<1|1, m+1, r, x); 
}
void upd(int from, int to, int val){
    while(chain[from] != chain[to]){
        int cur = chain[from];  
        Upd(1, 1, n, p[head[cur]], p[from], val);
        from = up[head[cur]][0];  
    } 
    Upd(1, 1, n, p[to], p[from], val);
}
int main(){
    cin >> n >> m; 
    f(i,0,m){
        cin >> U[i] >> V[i]; 
        if(U[i] != V[i]) 
            adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]); 
    }

    f(i,1,n+1) if(tin[i] == 0) dfs(i, 0); 
    f(i,1,n+1) 
        if(!vis[i]){
            head[++co] = i; 
            HLD(i, 0); 
        }
    cin >> q; 
    f(i,0,q){
        int u, v; 
        cin >> u >> v; 
        if(color[u] == color[v]) continue; 
        
        int LCA = lca(u, v), x; 
        if(u != LCA){
            x = node(u, LCA); 
            upd(u, x, 1); 
        }
        if(v != LCA){
            x = node(v, LCA); 
            upd(v, x, -1); 
        }
    }
    f(i,1,n+1){
        if(is_bridge[i]) direction[i] = Query(1, 1, n, p[i]); 
    }
    f(i,0,m){
        if((pa[U[i]] == V[i] and direction[U[i]] == 1) or (pa[V[i]] == U[i] and direction[V[i]] == -1)) cout << 'R'; 
        else if((pa[U[i]] == V[i] and direction[U[i]] == -1) or (pa[V[i]] == U[i] and direction[V[i]] == 1)) cout << 'L'; 
        else cout << 'B'; 
    }
    cout << "\n"; 
    return 0;  
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5012 KB Output is correct
3 Correct 3 ms 5136 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5268 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5236 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5012 KB Output is correct
3 Correct 3 ms 5136 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5268 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5236 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 57 ms 12236 KB Output is correct
12 Correct 65 ms 14980 KB Output is correct
13 Correct 79 ms 18920 KB Output is correct
14 Correct 100 ms 23720 KB Output is correct
15 Correct 108 ms 25032 KB Output is correct
16 Correct 115 ms 24088 KB Output is correct
17 Correct 115 ms 26700 KB Output is correct
18 Correct 128 ms 24928 KB Output is correct
19 Correct 116 ms 28048 KB Output is correct
20 Correct 75 ms 17608 KB Output is correct
21 Correct 77 ms 17744 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5012 KB Output is correct
3 Correct 3 ms 5136 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5268 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5236 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 57 ms 12236 KB Output is correct
12 Correct 65 ms 14980 KB Output is correct
13 Correct 79 ms 18920 KB Output is correct
14 Correct 100 ms 23720 KB Output is correct
15 Correct 108 ms 25032 KB Output is correct
16 Correct 115 ms 24088 KB Output is correct
17 Correct 115 ms 26700 KB Output is correct
18 Correct 128 ms 24928 KB Output is correct
19 Correct 116 ms 28048 KB Output is correct
20 Correct 75 ms 17608 KB Output is correct
21 Correct 77 ms 17744 KB Output is correct
22 Correct 273 ms 28044 KB Output is correct
23 Correct 315 ms 26108 KB Output is correct
24 Correct 300 ms 26268 KB Output is correct
25 Correct 276 ms 31752 KB Output is correct
26 Correct 303 ms 27524 KB Output is correct
27 Correct 312 ms 26168 KB Output is correct
28 Correct 70 ms 8180 KB Output is correct
29 Correct 216 ms 18332 KB Output is correct
30 Correct 257 ms 18696 KB Output is correct
31 Correct 158 ms 18888 KB Output is correct
32 Correct 234 ms 23276 KB Output is correct