제출 #521412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521412		Wayne_Yan	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	152 ms	29256 KiB

oneway

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int maxN = 1e5+10;
vector<int> edge[maxN];
int depth[maxN];
int low[maxN];
bool visited[maxN];
stack<int> st;
int bcc[maxN];

vector<int> t_edge[maxN];

void tarjan(int c, int p){
  depth[c] = (p ? depth[p] + 1 : 0);
  low[c] = depth[c];
  visited[c] = true;
  st.push(c);
  
  int cnt_fa = 0;
  for(int i : edge[c]){
    if(i == p && !cnt_fa){
      cnt_fa = 1;
      continue;
    }
    if(visited[i]){
      cmin(low[c], depth[i]);
    }else{
      tarjan(i, c);
      cmin(low[c], low[i]);
    }
  }
  
  if(low[c] == depth[c]){
    int tmp = st.top();
    do{
      tmp = st.top();
      bcc[tmp] = c;
      st.pop();
    }while(tmp != c);
  }
}

int ST[18][maxN];
int fa[maxN];

pii tab[maxN];
char ans[maxN];

int dsu[2][maxN]; // 0 down, 1 up.

int query(int i, int a){
  return dsu[i][a] == a ? a : dsu[i][a] = query(i, dsu[i][a]);
}

void merge(int i, int a, int b){
  if(query(i, a) != query(i, b)) dsu[i][query(i, a)] = query(i, b);
}

int t_depth[maxN];
bool t_visited[maxN];

void dfs(int c, int p){
  t_visited[c] = true;
  t_depth[c] = ( p ? t_depth[p] + 1 : 0);
  for(int i : t_edge[c]){
    if(i == p) continue;
    dfs(i, c);
  }
}


int LCA(int x, int y){
  if(t_depth[x] < t_depth[y]) swap(x,y);
  int c = t_depth[x] - t_depth[y];
  F(18) if( (c >> i) & 1) x = ST[i][x];
  if(x == y) return x;
  RF(18){
    if( ST[i][x] && ST[i][y] && ST[i][x] != ST[i][y]){
      x = ST[i][x];
      y = ST[i][y];
    }
  }
  x = ST[0][x];
  y = ST[0][y];
  return x;
}

void process(int x, int y){
  int c = LCA(x,y);
  while( t_depth[x] > t_depth[c] ){
    if(dsu[1][x] != x){
      x = dsu[1][x];
    }else{
      merge(1, x, ST[0][x]);
      x = ST[0][x];
    }
  }
  while( t_depth[y] > t_depth[c] ){
    if(dsu[0][y] != y){
      y = dsu[0][y];
    }else{
      merge(0, y, ST[0][y]);
      y = ST[0][y];
    }
  }
}


signed main(){
  
  iota(dsu[0], dsu[0] + maxN, 0);
  iota(dsu[1], dsu[1] + maxN, 0);
  
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  F(m){
    int x,y;
    cin >> x >> y;
    edge[x].pb(y);
    edge[y].pb(x);
    tab[i] = mp(x,y);
  }

  F(n) if(!visited[i+1]) tarjan(i+1, 0);
  
  Fi(x, m){
    auto [i,j] = tab[x];
    if(bcc[i] != bcc[j]){
      t_edge[bcc[i]].pb(bcc[j]);
      t_edge[bcc[j]].pb(bcc[i]);
      if(depth[bcc[i]] > depth[bcc[j]]){
        ST[0][bcc[i]] = fa[bcc[i]] = bcc[j];
      }else{
        ST[0][bcc[j]] = fa[bcc[j]] = bcc[i];
      }
    }
  }
  
  Fl(i, 1, n+1){
    if(!t_visited[bcc[i]]) dfs( bcc[i], 0);
  }

  Fl(i, 1, 18){
    Fi(j, maxN){
      ST[i][j] = ST[i-1][ST[i-1][j]];
    }
  }

  int p;
  cin >> p;
  
  F(p){
    int x,y;
    cin >> x >> y;
    x = bcc[x], y = bcc[y];
    process(x,y);
  }
  
  Fi(x, m){
    auto [i,j] = tab[x];
    i = bcc[i], j = bcc[j];
    if(i != j){
      if(query(0, i) == query(0, j)){
        if(t_depth[i] < t_depth[j]){
          ans[x] = 'R';
        }else{
          ans[x] = 'L';
        }
      }else if(query(1,i) == query(1, j)){
        if(t_depth[i] < t_depth[j]){
          ans[x] = 'L';
        }else{
          ans[x] = 'R';
        }
      }else{
        ans[x] = 'B';
      }
    }else{
      ans[x] = 'B';
    }
  }
  
  F(m) printf("%c", ans[i]);
   
  return 0;
}

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