Submission #101372

#	Time	Username	Problem	Language	Result	Execution time	Memory
101372		Milki	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	336 ms	35064 KiB

oneway

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5, LOG = 17;

int n, m, p, tijme, low[MAXN], start[MAXN], anc[LOG][MAXN], sol[MAXN], dep[MAXN], deg[MAXN];
vector <point> E1[MAXN], E[MAXN];
bool bio[MAXN], bridge[MAXN];
point edge[MAXN];

void load(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> m;
  REP(i, m){
    int a, b; cin >> a >> b; a --; b --;
    E1[a].pb(point(b, i)); E1[b].pb(point(a, i));
    edge[i] = point(a, b);
  }
}

void dfsBridge(int x, int par = -1){
  bio[x] = true;
  start[x] = low[x] = tijme ++;

  for(auto e : E1[x]){
    if(e.second == par) continue;
    if(bio[e.first])
      low[x] = min(low[x], start[e.first]);
    else{
      dfsBridge(e.first, e.second);
      low[x] = min(low[x], low[e.first]);
      if(low[e.first] > start[x])
        bridge[e.second] = true;
    }
  }
}

void findBridges(){
  REP(i, n)
    if(!bio[i])
      dfsBridge(i);
}

int comp[MAXN];

void dfsGraph(int x, int color){
  comp[x] = color;
  bio[x] = true;
  for(auto e : E1[x]){
    if(bio[e.first]) continue;
    if(bridge[e.second]){
      E[color].pb(point(tijme + 1, e.second));
      E[tijme + 1].pb(point(color, e.second));
      dfsGraph(e.first, ++tijme);
    }
    else
      dfsGraph(e.first, color);
  }
}

void createGraph(){
  memset(bio, 0, sizeof(bio));
  tijme = -1;

  REP(i, n)
    if(!bio[i])
      dfsGraph(i, ++tijme);
  tijme ++;

  REP(i, tijme){
    sort(E[i].begin(), E[i].end());
    E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());
  }
}

vector <int> leaf;

void dfsLca(int x, int par = -1){
  int cnt = 0;
  bio[x] = true;

  for(auto e : E[x]){
    if(e.first == par) continue;
    cnt ++;
    dep[e.first] = dep[x] + 1;
    anc[0][e.first] = x;
    //cout <<"veza " << x _ e.first << "\n";
    dfsLca(e.first, x);
  }
  if(cnt == 0)
    leaf.pb(x);
  else
    deg[x] = cnt;
}

void computeLca(){
  memset(bio, 0, sizeof(bio));
  REP(i, tijme)
    if(!bio[i])
      dfsLca(i);
  FOR(i, 1, LOG) REP(j, tijme){
    int x = anc[i - 1][j];
    anc[i][j] = anc[i - 1][x];
  }
}

int getLca(int x, int y){
  if(x == y) return x;
  if(dep[x] < dep[y]) swap(x, y);

  for(int i = LOG - 1; i >= 0; --i)
    if(dep[x] - (1 << i) >= dep[y])
      x = anc[i][x];
  if(x == y) return x;

  for(int i = LOG - 1; i >= 0; --i){
    if(anc[i][x] != anc[i][y]){
      x = anc[i][x];
      y = anc[i][y];
    }
  }
  return anc[0][x];
}

vector <int> gdje[MAXN];
int suma[MAXN];

void solve(){
  cin >> p;
  REP(i, p){
    int a, b; cin >> a >> b; a --; b --;
    a = comp[a]; b = comp[b];
    if( a == b ) continue;
    //cout << "comp " << a _ b << "\n";
    int x = getLca(a, b);
    if(a == x){
      gdje[b].pb(-1);
      gdje[x].pb(1);
      //cout << b _ -1 _ x _ 1 << " ubacujem\n";
      //cout << a _ b << " prvo\n";
    }
    else if(b == x){
      gdje[a].pb(1);
      gdje[x].pb(-1);
      //cout << a _ b << " drugo\n";
    }
    else{
      gdje[a].pb(1);
      gdje[b].pb(-1);
      //cout << a _ 1 _ b _ -1 << " ubacujem\n";
    } // 1 dizem    -1 spustam
  }
  queue <int> Q;
  for(auto it : leaf){
    Q.push(it);
  }

  while(!Q.empty()){
    int x = Q.front(); Q.pop();

    for(auto it : gdje[x])
      suma[x] += it;
    //cout << suma[x] _ x << " suma i x\n";
    for(auto e : E[x]){
      if(deg[e.first] == 0) continue;
      deg[e.first] --;
      suma[e.first] += suma[x];

      if(suma[x] > 0){
        if(comp[edge[e.second].first] == x) sol[e.second] = 1;
        else sol[e.second] = -1;
      }
      else if(suma[x] < 0){
        if(comp[edge[e.second].first] == x) sol[e.second] = -1;
        else sol[e.second] = 1;
      }

      if(deg[e.first] == 0)
        Q.push(e.first);
    }
  }

  REP(i, m){
    if(sol[i] == -1) cout << 'L';
    else if(sol[i] == 0) cout << 'B';
    else cout << 'R';
  }
}

int main(){
  load();
  findBridges();
  createGraph();
  computeLca();
  solve();
}

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