Submission #761056

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

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40