제출 #238386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238386		nickmet2004	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	7 ms	5504 KiB

oneway

#include<bits/stdc++.h>
#define f first
#define s second

using namespace std;

const int N = 1e5 + 5;
typedef pair<int , int> ipair;
int n , m;
vector<ipair> adj[N] , newG[N];
int vis[N] , bridges[N] , disc[N] , low[N] , comp[N] , sum[N];
ipair edges[N];
char ans[N];

void ini(){memset(vis , 0 , sizeof(vis));}
int dtime;
void dfs(int u , int p){
    vis[u] = 1;
    disc[u] = low[u] = dtime++;
    for(ipair X : adj[u]){
        int v = X.f , id = X.s;
        if(v == p) continue;
        if(!vis[v]){
            dfs(v , u);
            if(disc[u] < low[v]) bridges[id] = 1;
            low[u] = min(low[u] , low[v]);
        } else low[u] = min(low[u] , disc[v]);
    }
}
void DFS(int u , int x){
    vis[u] = 1;
    comp[u] = x;
    for(ipair X : adj[u]){
        int v = X.f , id = X.s;
        if(!bridges[id] && !vis[v]) DFS(v , x);
    }
}
void go(int u  , int p){
    vis[u] = 1;
    for(ipair X : newG[u]){
        int v = X.f , id = X.s;
        if(v == p) continue;
        go(v , u);
        sum[u] += sum[v];
        if(sum[v] > 0){
            if(edges[id].f == v) ans[id] = 'L'; else ans[id] = 'R';
        }
        if(sum[v] < 0){
            if(edges[id].f == u) ans[id] = 'R'; else ans[id] = 'L';
        }
    }
}

int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u , v;
        cin >> u >> v; --u; --v;
        adj[u].emplace_back(v , i); adj[v].emplace_back(u , i);
        edges[i].f = u; edges[i].s = v;
    }
    ini();
    for(int i = 0; i < n; ++i){
        if(!vis[i]) dfs(i , -1);
    }
    ini();
    int cmp = 0;
    for(int i = 0; i < n; ++i){
        if(!vis[i]){
            DFS(i , cmp);
            cmp++;
        }
    }
    //cerr << "pk";
    //cerr << cmp << " C " << endl;
    for(int i = 0; i < m; ++i){
        int cu = comp[edges[i].f] , cv = comp[edges[i].s];
      //  cerr << cu << " cu " << cv << " cv " << endl;
        if(bridges[i]){
            newG[cu].emplace_back(cv , i);
            newG[cv].emplace_back(cu , i);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int u , v;
        cin >> u >> v; --u; --v;
        sum[comp[u]]++; sum[comp[v]]--;
    }
    ini();
    for(int i = 0; i < cmp; ++i){
        if(!vis[i]) go(i , -1);
    }
    for(int i = 0; i < m; ++i){
        if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B';
    }
    cout << ans;

return 0;
}

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