Submission #115212

#	Time	Username	Problem	Language	Result	Execution time	Memory
115212		IOrtroiii	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	170 ms	22340 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m, q;
bool visit[N];
int p[N], ans[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> g2[N];
int num[N], low[N], tt;
int par[N], parid[N], dep[N];
vector<tuple<int, int, int>> tr;

int getp(int u) {
   if (p[u] == u) {
      return u;
   } else {
      return p[u] = getp(p[u]);
   }
}

void mrg(int u, int v) {
   p[getp(v)] = getp(u);
}

void dfs(int u, int pid) {
   num[u] = low[u] = ++tt;
   for (auto e : g[u]) {
      int v, id; tie(v, id) = e;
      if (id + pid) {
         if (num[v]) low[u] = min(low[u], num[v]);
         else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > num[u]) {
               tr.emplace_back(u, v, id);
            } else mrg(u, v);
         }
      }
   }
}

void dfs2(int u, int p) {
   visit[u] = true;
   for (auto e : g2[u]) {
      int v, id; tie(v, id) = e;
      if (v ^ p) {
         par[v] = u;
         parid[v] = -id;
         dep[v] = dep[u] + 1;
         dfs2(v, u);
      }
   }
}

int main() {
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= n; ++i) p[i] = i;
   for (int i = 1; i <= m; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      g[u].emplace_back(v, i);
      g[v].emplace_back(u, -i);
   }
   for (int i = 1; i <= n; ++i) {
      if (!num[i]) dfs(i, 0);
   }
   for (auto e : tr) {
      int u, v, id; tie(u, v, id) = e;
      u = getp(u), v = getp(v);
      g2[u].emplace_back(v, id);
      g2[v].emplace_back(u, -id);
   }
   for (int i = 1; i <= n; ++i) {
      if (p[i] == i && !visit[i]) dfs2(i, 0);
   }
   scanf("%d", &q);
   while (q--) {
      int u, v;
      scanf("%d %d", &u, &v);
      u = getp(u), v = getp(v);
      while (u ^ v) {
         if (dep[u] > dep[v]) {
            if (parid[u] > 0) ans[parid[u]] = 1;
            else ans[-parid[u]] = 2;
            mrg(par[u], u);
            u = getp(u);
         } else {
            if (parid[v] > 0) ans[parid[v]] = 2;
            else ans[-parid[v]] = 1;
            mrg(par[v], v);
            v = getp(v);
         }
      }
   }
   for (int i = 1; i <= m; ++i) {
      if (ans[i] == 0) putchar('B');
      else if (ans[i] == 1) putchar('R');
      else putchar('L');
   }
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:63:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &u, &v);
       ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &q);
    ~~~~~^~~~~~~~~~
oneway.cpp:82:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &u, &v);
       ~~~~~^~~~~~~~~~~~~~~~~

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