Submission #230699

#	Time	Username	Problem	Language	Result	Execution time	Memory
230699		AlexLuchianov	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	393 ms	34940 KiB

oneway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40