oj.uz

Submission #101372

# Submission time Handle Problem Language Result Execution time Memory
101372 2019-03-18T18:41:37 Z Milki One-Way Streets (CEOI17_oneway) C++14
100 / 100
 336 ms 35064 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.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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7680 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 9 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 8 ms 7808 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 9 ms 7680 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7680 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 9 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 8 ms 7808 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 9 ms 7680 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct
11 Correct 58 ms 13732 KB Output is correct
12 Correct 77 ms 14740 KB Output is correct
13 Correct 111 ms 16368 KB Output is correct
14 Correct 130 ms 19576 KB Output is correct
15 Correct 148 ms 21040 KB Output is correct
16 Correct 151 ms 26740 KB Output is correct
17 Correct 149 ms 28124 KB Output is correct
18 Correct 137 ms 26868 KB Output is correct
19 Correct 144 ms 29176 KB Output is correct
20 Correct 79 ms 14328 KB Output is correct
21 Correct 54 ms 14584 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7680 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 9 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 8 ms 7808 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 9 ms 7680 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct
11 Correct 58 ms 13732 KB Output is correct
12 Correct 77 ms 14740 KB Output is correct
13 Correct 111 ms 16368 KB Output is correct
14 Correct 130 ms 19576 KB Output is correct
15 Correct 148 ms 21040 KB Output is correct
16 Correct 151 ms 26740 KB Output is correct
17 Correct 149 ms 28124 KB Output is correct
18 Correct 137 ms 26868 KB Output is correct
19 Correct 144 ms 29176 KB Output is correct
20 Correct 79 ms 14328 KB Output is correct
21 Correct 54 ms 14584 KB Output is correct
22 Correct 279 ms 32092 KB Output is correct
23 Correct 274 ms 30660 KB Output is correct
24 Correct 265 ms 31020 KB Output is correct
25 Correct 291 ms 35064 KB Output is correct
26 Correct 336 ms 31892 KB Output is correct
27 Correct 249 ms 30580 KB Output is correct
28 Correct 42 ms 11640 KB Output is correct
29 Correct 82 ms 16092 KB Output is correct
30 Correct 84 ms 16504 KB Output is correct
31 Correct 116 ms 16140 KB Output is correct
32 Correct 187 ms 22904 KB Output is correct