oj.uz

Submission #230699

# Submission time Handle Problem Language Result Execution time Memory
230699 2020-05-11T08:28:38 Z AlexLuchianov One-Way Streets (CEOI17_oneway) C++14
100 / 100
 393 ms 34940 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <set>

using namespace std;

int const nmax = 100000;
int const lgmax = 20;

vector<int> g[1 + nmax];
int edge[1 + nmax][2];
int level[1 + nmax], seen[1 + nmax];
int maxlevel[1 + nmax], comp[1 + nmax];

void dfs(int node, int parent){
  level[node] = level[parent] + 1;
  maxlevel[node] = level[node];
  seen[node] = 1;
  int skipped = 0;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to == parent && skipped == 0){
      skipped++;
      continue;
    }

    if(seen[to] == 0) {
      dfs(to, node);
      if(maxlevel[to] < maxlevel[node])
        maxlevel[node] = maxlevel[to];
    } else if(level[to] < maxlevel[node])
      maxlevel[node] = level[to];
  }
}

void _partition(int node, int parent, int &ptr){
  seen[node] = 1;
  if(maxlevel[node] <= level[parent])
    comp[node] = comp[parent];
  else
    comp[node] = ++ptr;

  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(seen[to] == 0)
      _partition(to, node, ptr);
  }
}

namespace Tree{
  vector<int> g[1 + nmax];
  set<pair<int,int>> edges;
  int far[1 + lgmax][1 + nmax], level[1 + nmax];

  void dfs(int node, int parent){
    far[0][node] = parent;
    level[node] = level[parent] + 1;
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(to != parent)
        dfs(to, node);
    }
  }
  void addedge(int x, int y){
    edges.insert({x, y});
    g[x].push_back(y);
    g[y].push_back(x);
  }

  void computefar(int n){
    for(int h = 1; h <= lgmax; h++)
      for(int i = 1;i <= n; i++)
        far[h][i] = far[h - 1][far[h - 1][i]];
  }

  int getlca(int x, int y){
    if(level[x] < level[y])
      swap(x, y);
    for(int h = lgmax; 0 <= h; h--)
      if(level[y] + (1 << h) <= level[x])
        x = far[h][x];
    if(x == y)
      return x;
    for(int h = lgmax; 0 <= h; h--)
      if(far[h][x] != far[h][y]){
        x = far[h][x];
        y = far[h][y];
      }
    return far[0][x];
  }

  int sum[1 + nmax][2];
  void mark(int x, int y, int p){
    sum[x][p]++;
    sum[y][p]--;
  }

  void refresh(int node, int parent){
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(to != parent) {
        refresh(to, node);
        sum[node][0] += sum[to][0];
        sum[node][1] += sum[to][1];
      }
    }
  }
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 1;i <= m; i++){
    int x, y;
    cin >> x >> y;
    if(x != y) {
      g[x].push_back(y);
      g[y].push_back(x);
    }
    edge[i][0] = x;
    edge[i][1] = y;
  }

  for(int i = 1;i <= n; i++)
    if(seen[i] == 0)
      dfs(i, 0);

  for(int i = 1;i <= n; i++)
    seen[i] = 0;
  int ptr = 0;

  for(int i = 1; i <= n; i++)
    if(seen[i] == 0)
      _partition(i, 0, ptr);

  for(int i = 1;i <= m; i++){
    int x = comp[edge[i][0]];
    int y = comp[edge[i][1]];
    if(y < x)
      swap(x, y);
    if(x != y && Tree::edges.find({x, y}) == Tree::edges.end())
      Tree::addedge(x, y);
  }

  Tree::dfs(1, 0);
  Tree::computefar(n);

  int q;
  cin >> q;
  for(int i = 1;i <= q; i++){
    int x, y;
    cin >> x >> y;
    x = comp[x];
    y = comp[y];

    if(x != y){
      int lca = Tree::getlca(x, y);
      Tree::mark(x, lca, 0);
      Tree::mark(y, lca, 1);
    }
  }

  Tree::refresh(1, 0);
  for(int i = 1;i <= m; i++){
    int x = comp[edge[i][0]];
    int y = comp[edge[i][1]];
    int lower = x;
    if(Tree::level[x] < Tree::level[y])
      lower = y;
    if(x == y || (0 == Tree::sum[lower][0] && 0 == Tree::sum[lower][1]))
      cout << "B";
    else if(0 < Tree::sum[lower][0]){
      if(x == lower)
        cout << "R";
      else
        cout << "L";
    } else {
      if(x == lower)
        cout << "L";
      else
        cout << "R";
    }
  }
  return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void _partition(int, int, int&)':
oneway.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void Tree::dfs(int, int)':
oneway.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void Tree::refresh(int, int)':
oneway.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5376 KB Output is correct
6 Correct 9 ms 5248 KB Output is correct
7 Correct 9 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5376 KB Output is correct
6 Correct 9 ms 5248 KB Output is correct
7 Correct 9 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 104 ms 11512 KB Output is correct
12 Correct 124 ms 13568 KB Output is correct
13 Correct 142 ms 16616 KB Output is correct
14 Correct 168 ms 21624 KB Output is correct
15 Correct 178 ms 23160 KB Output is correct
16 Correct 261 ms 29304 KB Output is correct
17 Correct 199 ms 30584 KB Output is correct
18 Correct 248 ms 29260 KB Output is correct
19 Correct 182 ms 31992 KB Output is correct
20 Correct 125 ms 15148 KB Output is correct
21 Correct 119 ms 14840 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5376 KB Output is correct
6 Correct 9 ms 5248 KB Output is correct
7 Correct 9 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 104 ms 11512 KB Output is correct
12 Correct 124 ms 13568 KB Output is correct
13 Correct 142 ms 16616 KB Output is correct
14 Correct 168 ms 21624 KB Output is correct
15 Correct 178 ms 23160 KB Output is correct
16 Correct 261 ms 29304 KB Output is correct
17 Correct 199 ms 30584 KB Output is correct
18 Correct 248 ms 29260 KB Output is correct
19 Correct 182 ms 31992 KB Output is correct
20 Correct 125 ms 15148 KB Output is correct
21 Correct 119 ms 14840 KB Output is correct
22 Correct 393 ms 31840 KB Output is correct
23 Correct 366 ms 30200 KB Output is correct
24 Correct 386 ms 30524 KB Output is correct
25 Correct 314 ms 34940 KB Output is correct
26 Correct 325 ms 31480 KB Output is correct
27 Correct 335 ms 30456 KB Output is correct
28 Correct 117 ms 8312 KB Output is correct
29 Correct 206 ms 15736 KB Output is correct
30 Correct 212 ms 15992 KB Output is correct
31 Correct 207 ms 16248 KB Output is correct
32 Correct 244 ms 22264 KB Output is correct