Submission #299131

#	Time	Username	Problem	Language	Result	Execution time	Memory
299131		istlemin	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	384 KiB

oneway

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

ll n,m,p;

vector<pii> d;
vector<vector<pii>> e;
vector<pii> edges;

vi dfsnum;
vi dfslow;
vector<bool> seen;
ll c = 0;

vector<vi> adj;

ll dfs3(ll v, ll le){
    if(seen[v]) return dfslow[v];
    seen[v] = true;
    dfsnum[v] = dfslow[v] = c++;

    if(le!=-1){
        //cout<<"tree edge "<< edges[le].first<<" "<<edges[le].second<<endl;
        adj[edges[le].first].push_back(edges[le].second);
        adj[edges[le].second].push_back(edges[le].first);
    }

    trav(up,e[v]){
        ll u,ed;
        tie(u,ed) = up;
        
        if(ed==le) continue;
        //cout<<v<<": "<<u<<endl;
        dfslow[v] = min(dfslow[v], dfs3(u,ed));
    }
    //cout<<v<<": "<<dfsnum[v]<<" "<<dfslow[v]<<endl;
    return dfslow[v];
}

vi height, par, visited;
vector<pii> u;
vector<vi> jump;
map<pii, ll> r;

void dfs(ll v, ll h, ll p){
    height[v] = h;
    par[v] = p;
    for(ll x : adj[v]){
        if(x != p) dfs(x, h+1, v);
    }
}

pii dfs2(ll v){
    //cout<<v<<endl;
    visited[v] = 1;
    pii h = u[v];
    for(ll x : adj[v]){
        //cout<<"x "<<x<<endl;
        if(x != par[v]) h = min(h, dfs2(x));
    }
    if(h.first < height[v]){
        //cout<<par[v]<<" "<< v<<" "<<h.second<<endl;
        r[{par[v], v}] = h.second;
        r[{v, par[v]}] = !h.second;
    }
    return h;
}

ll goup(ll from, ll steps){
    for(ll i = 0; i < 20; i++){
        if(steps&(1<<i)) from = jump[from][i];
        if(from==-1) return -1;
    }
    return from;
}

ll lca(ll a, ll b){
    if(height[a] < height[b]) swap(a, b);
    //cout<<"heights: "<<height[a]<<" "<<height[b]<<endl;
    //cout<<a<<" "<<b<<endl;
    a = goup(a, height[a]-height[b]);
    for(ll i = 19; i >= 0; i--){
        //cout<<a<<" "<<b<<endl;
        ll ta = jump[a][i];
        ll tb = jump[b][i];
        if(ta != tb) a=ta, b=tb;
    }
    return par[a];
}

void solvetree(){
    height = visited = vi(n);
    u = vector<pii>(n, {INT32_MAX, 0});
    par = vi(n, -2);
    for(ll i = 0; i < n; i++) if(par[i] == -2) dfs(i, 0, -1);

    //cout<<"adj:"<<endl;
    /*trav(us,adj) {
        trav(u,us) //cout<<u<<" ";
        //cout<<endl;
    }*/

    //cout<<"h:"<<endl;
    trav(h,height) //cout<<h<<endl;

    jump = vector<vi>(n, vi(20));
    for(ll i = 0; i < n; i++){
        jump[i][0] = par[i];
    }
    for(ll i = 1; i < 20; i++){
        for(ll j = 0; j < n; j++){
            jump[j][i] = jump[j][i-1]==-1?-1:jump[jump[j][i-1]][i-1];
        }
    }
    for(ll i = 0; i < p; i++){
        ll a = d[i].first;
        ll b = d[i].second;
        ll l = lca(a, b);
        u[a] = {l, 1};
        u[b] = {l, 0};
    }
    for(ll i = 0; i < n; i++){
        if(!visited[i]) dfs2(i);
    }
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    cin>>n>>m;

    e.resize(n);
    adj.resize(n);

    rep(i,0,m) {
        ll a,b;
        cin>>a>>b;
        --a;--b;
        edges.emplace_back(a,b);
        e[a].emplace_back(b,i);
        e[b].emplace_back(a,i);

        //cout<<"edge "<<a<<" "<<b<<endl;
    }
    cin>>p;
    d.resize(p);
    rep(i,0,p) {
        ll a,b;
        cin>>a>>b;
        --a;--b;
        d[i] = {a,b};
    }

    dfsnum.resize(n);
    dfslow.resize(n);
    seen.resize(n);

    rep(i,0,n)
        dfs3(i,-1);

    vi bridges;
    rep(i,0,m){
        ll a,b;
        tie(a,b) = edges[i];

        if(dfsnum[a]>dfsnum[b]) swap(a,b);

        if(dfslow[b]==dfsnum[b]){
            bridges.push_back(i);
            //cout<<"bridge: "<<a<<" "<<b<<endl;
        }
    }
    
    solvetree();

    string ans(m,'B');

    trav(b,bridges){
        pair<ll,ll> ed = edges[b];
        if(r.find(ed)!=r.end())
            ans[b] = "RL"[r[ed]];
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

oneway.cpp: In function 'void solvetree()':
oneway.cpp:115:10: warning: unused variable 'h' [-Wunused-variable]
  115 |     trav(h,height) //cout<<h<<endl;
      |          ^
oneway.cpp:8:30: note: in definition of macro 'trav'
    8 | #define trav(a, x) for(auto& a : x)
      |                              ^

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