제출 #67537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67537		MiricaMatei	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	798 ms	55052 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;

struct Edge {
  int a, b;
  int other(int node) {
    return a ^ b ^ node;
  }
}e[MAX_N + 5];

vector<int>G[MAX_N + 5];
int h[MAX_N + 5], low[MAX_N + 5];
bool viz[MAX_N + 5];

int t1[MAX_N + 5], h1[MAX_N + 5];
int indcomp[MAX_N + 5];
vector<int>comp[MAX_N + 5];

vector<int>G1[MAX_N + 5];
int t2[MAX_N + 5], h2[MAX_N + 5];
int niv[MAX_N + 5], f[MAX_N + 5];
int mp[MAX_N + 5], nd[MAX_N + 5];

char sol[MAX_N + 5];

int f1(int x) {
  int y = x;
  while (x != t1[x])
    x = t1[x];
  while (y != t1[y]) {
    int aux = t1[y];
    t1[y] = x;
    y = aux;
  }
  return x;
}

void u1(int x, int y) {
  x = f1(x);
  y = f1(y);
  if (x == y)
    return ;
  if (h1[y] > h1[x])
    swap(x, y);
  t1[y] = x;
  if (h1[x] == h1[y])
    h1[x]++;
}

void dfs(int nod, int ff) {
  viz[nod] = 1;
  for (auto it:G[nod]) {
    int v = e[it].other(nod);
    if (!viz[v]) {
      low[v] = h[v] = h[nod] + 1;
      dfs(v, it);
      low[nod] = min(low[nod], low[v]);
      if (low[v] <= h[nod])
        u1(nod, v);
    } else if (it != ff) {
      low[nod] = min(low[nod], h[v]);
    }
  }
}

void solve1(int nod, int ff) {
  viz[nod] = 1;
  for (auto it:G[nod])
    if (it != ff) {
      int v = e[it].other(nod);
      if (indcomp[nod] == indcomp[v]) {
        sol[it] = 'B';
        if (!viz[v])
          solve1(v, it);
      }
    }
}

int other(int it, int nod) {
  if (indcomp[e[it].a] == nod)
    return e[it].b;
  return e[it].a;
}

void dfs2(int nod, int ff) {
  viz[nod] = 1;
  for (auto it:G1[nod]) {
    int v = indcomp[other(it, nod)];
    if (v != ff) {
      niv[v] = 1 + niv[nod];
      f[v] = nod;
      mp[v] = it;
      dfs2(v, nod);
    }
  }
}

int f2(int x) {
  int y = x;
  while (t2[x] != x)
    x = t2[x];
  while (y != t2[y]) {
    int aux = t2[y];
    t2[y] = x;
    niv[y] = niv[x];
    nd[y] = nd[x];
    y = aux;
  }
  return x;
}

void u2(int x, int y) {
  x = f2(x);
  y = f2(y);
  if (x == y)
    return ;
  if (h[y] > h[x])
    swap(x, y);
  t2[y] = x;
  if (h2[x] == h2[y])
    h2[x]++;
  if (niv[y] < niv[x]) {
    niv[x] = niv[y];
    nd[x] = nd[y];
  }
}

void solve2(int a, int b) {
  if (sol[mp[a]])
    a = nd[f2(a)];
  if (sol[mp[b]])
    b = nd[f2(b)];
  while (a != b) {
    if (niv[a] > niv[b]) {
      int aux = f[a];
      if (indcomp[e[mp[a]].a] == a)
        sol[mp[a]] = 'R';
      else
        sol[mp[a]] = 'L';
      u2(aux, a);
      if (sol[mp[f[a]]]) {
        u2(a, f[a]);
        a = nd[f2(a)];
      } else {
        a = aux;
      }
    } else {
      int aux = f[b];
      if (indcomp[e[mp[b]].a] == b)
        sol[mp[b]] = 'L';
      else
        sol[mp[b]] = 'R';
      u2(aux, b);
      if (sol[mp[f[b]]]) {
        u2(b, f[b]);
        b = nd[f2(b)];
      } else {
        b = aux;
      }
    }
  }
}

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[i] = {x, y};
    G[x].push_back(i);
    G[y].push_back(i);
  }

  for (int i = 1; i <= n; ++i)
    t1[i] = t2[i] = nd[i] = i;

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

  for (int i = 1; i <= n; ++i) {
    int aux = f1(i);
    indcomp[i] = aux;
    comp[aux].push_back(i);
  }

  for (int i = 1; i <= n; ++i)
    if ((int)comp[i].size() > 0) {
      memset(viz, 0, sizeof(viz));
      solve1(comp[i][0], 0);
    }

  for (int i = 1; i <= m; ++i)
    if (indcomp[e[i].a] != indcomp[e[i].b]) {
      G1[indcomp[e[i].a]].push_back(i);
      G1[indcomp[e[i].b]].push_back(i);
    }

  memset(viz, 0, sizeof(viz));
  for (int i = 1; i <= n; ++i)
    if (!viz[indcomp[i]])
      dfs2(indcomp[i], 0);

  int p;
  scanf("%d", &p);
  for (int i = 1; i <= p; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (indcomp[x] != indcomp[y])
      solve2(indcomp[x], indcomp[y]);
  }

  for (int i = 1; i <= m; ++i) {
    if (!sol[i])
      sol[i] = 'B';
    printf("%c", sol[i]);
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:212:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p);
   ~~~~~^~~~~~~~~~
oneway.cpp:215:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~

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