oj.uz

답안 #299212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299212 2020-09-14T14:52:50 Z istlemin One-Way Streets (CEOI17_oneway) C++14
0 / 100
 72 ms 1024 KB 
#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 && edges[le].first!=edges[le].second){
        //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]){
        if(x != par[v]) {
            h = min(h, dfs2(x));
        }
    }
    if(h.first < height[v]){
        //cout<<par[v]+1<<" "<<v+1<<" "<<h.second<<endl;
        r[{par[v], v}] = h.second;
        r[{v, par[v]}] = !h.second;
    }
    //cout<<v+1<<": "<<h.first<<" "<<height[v]<<" "<<u[v].first<<endl;
    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;
    }
    if(a==b) return a;
    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;
        if(a==b) continue;
        ll l = lca(a, b);
        //cout<<a<<" "<<l<<endl;
        //cout<<b<<" "<<l<<endl;
        u[a] = min(u[a], {height[l], 1});
        u[b] = min(u[a], {height[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() && ed.first!=ed.second)
            ans[b] = "RL"[r[ed]];
    }
    cout<<ans<<endl;
}

Compilation message

oneway.cpp: In function 'void solvetree()':
oneway.cpp:118:10: warning: unused variable 'h' [-Wunused-variable]
  118 |     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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 22 ms 1024 KB Output is correct
4 Correct 68 ms 960 KB Output is correct
5 Incorrect 72 ms 1024 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 22 ms 1024 KB Output is correct
4 Correct 68 ms 960 KB Output is correct
5 Incorrect 72 ms 1024 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 22 ms 1024 KB Output is correct
4 Correct 68 ms 960 KB Output is correct
5 Incorrect 72 ms 1024 KB Output isn't correct
6 Halted 0 ms 0 KB -