oj.uz

답안 #238552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238552 2020-06-11T18:56:10 Z nickmet2004 One-Way Streets (CEOI17_oneway) C++11
0 / 100
 8 ms 5504 KB 
#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];
int vis[N] , bridges[N] , disc[N] , low[N] , comp[N] , sum[N] , most[N];
ipair edges[N];
char ans[N];
struct Node{
    int cmp , id , u , v;
};
vector<Node>newG[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;
    most[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(Node X : newG[u]){
        int v = X.cmp , id = X.id , U = X.u , V = X.v;
        if(v == p) continue;
        go(v , u);
        sum[u] += sum[v];
        //cout << sum[v] << endl;
        if(sum[v] > 0){
            //cout << edges[id].f << " edges[i].f " << v << " v "<< endl;
          //  cout << edges[id].f << " u " << edges[id].s << " v " << endl;
            if(edges[id].f == V){
                ans[id] = 'R';
               // cout << edges[id].f << " edges[i].f " << endl;
            }
            else{
                ans[id] = 'L';
            }
        }
        if(sum[v] < 0){
          //  cout << edges[id].f << " u " << edges[id].s << " v " << endl;
           // cout << edges[id].f << " edges[i].f " << u << " u " << endl;
            if(edges[id].f == U) ans[id] = 'R'; else ans[id] = 'L';
        }
    }
   // cout << sum[u] << " sum " << endl;
}

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].push_back({cv , i , edges[i].f , edges[i].s});
            newG[cv].push_back({cu , i , edges[i].s , edges[i].f});
        }
    }
    int q;
    cin >> q;
    while(q--){
        int u , v;
        cin >> u >> v; --u; --v;
        sum[comp[u]]++; sum[comp[v]]--;
    }
    ini();
    sort(most , most + cmp); reverse(most , most + cmp);
    for(int i = 0; i < cmp; ++i){
        if(!vis[most[i]]) go(most[i] , -1);
    }
    for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B';
    for(int i = 0; i < m; ++i) cout << ans[i];
return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -