제출 #238785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238785		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];
int vis[N] , bridges[N] , disc[N] , low[N] , comp[N] , sum[N] , most[N] , KK[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;
       // if(vis[v]) 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 = 1; i <= m; ++i){
        int u , v;
        cin >> u >> v;
        adj[u].emplace_back(v , i); adj[v].emplace_back(u , i);
        edges[i].f = u; edges[i].s = v; ans[i] = 'B';
    }
    ini();
    for(int i = 1; i <= n; ++i){
        KK[i] = i;
        if(!vis[i]) dfs(i , -1);
    }
    ini();
    int cmp = 0;
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            DFS(i , cmp);
            cmp++;
        }
    }
    //cerr << "pk";
    //cerr << cmp << " C " << endl;
    for(int i = 1; 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;
        if(comp[u] == comp[v]) continue;
        sum[comp[u]]++; sum[comp[v]]--;
    }
    ini();
   // sort(KK + 1, KK + n + 1 , COMP); //reverse(most , most + cmp);
    for(int i = 1; i <= n; ++i){
        if(!vis[comp[i]]) go(comp[i] , -1);
    }for(int i = 1; i <= m; ++i) cout << ans[i];
return 0;
}

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