oj.uz

Submission #101368

# Submission time Handle Problem Language Result Execution time Memory
101368 2019-03-18T17:40:51 Z Milki One-Way Streets (CEOI17_oneway) C++14
0 / 100
 11 ms 7808 KB 
#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.first == par) continue;
    if(bio[e.first])
      low[x] = min(low[x], start[e.first]);
    else{
      dfsBridge(e.first, x);
      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 if(sol[i] == 1) cout << 'R';
    else assert(false);
  }
}

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 11 ms 7680 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 11 ms 7780 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct
7 Correct 11 ms 7808 KB Output is correct
8 Correct 10 ms 7808 KB Output is correct
9 Incorrect 10 ms 7668 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 11 ms 7680 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 11 ms 7780 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct
7 Correct 11 ms 7808 KB Output is correct
8 Correct 10 ms 7808 KB Output is correct
9 Incorrect 10 ms 7668 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 11 ms 7680 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 11 ms 7780 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct
7 Correct 11 ms 7808 KB Output is correct
8 Correct 10 ms 7808 KB Output is correct
9 Incorrect 10 ms 7668 KB Output isn't correct
10 Halted 0 ms 0 KB -