Submission #564060

#	Time	Username	Problem	Language	Result	Execution time	Memory
564060		hoanghq2004	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	80 ms	20544 KiB

oneway

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int n, m, cnt, q;
vector <int> e[N], stk;
vector <pair <int, int> > g[N];
int num[N], low[N], ti, comp[N], w[N];
 
void dfs(int u, int p) {
    stk.push_back(u);
    low[u] = num[u] = ++ti;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i].first;
        int id = g[u][i].second;
        if (id == p) continue;
        if (comp[v]) continue;
        if (!num[v]) {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
        } else low[u] = min(low[u], num[v]);
    }
    if (low[u] == num[u]) {
        ++m;
        while (stk.size()) {
            int v = stk.back();
            stk.pop_back();
            comp[v] = m;
            for (auto w: g[v]) {
                if (comp[w.first] && m != comp[w.first]) e[m].push_back(comp[w.first]);
            }
            if (v == u) break;
        }
    }
}
 
void pull(int u) {
    num[u] = 1;
    for (auto v: e[u]) {
        if (!num[v]) pull(v);
        w[u] += w[v];
    }
}
 
int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    vector <pair <int, int> > edges;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        edges.push_back({u, v});
    }
    m = 0;
    for (int i = 1; i <= n; ++i) {
        if (num[i]) continue;
        dfs(i, 0);
    }
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        u = comp[u], v = comp[v];
        if (u == v) continue;
        ++w[u], --w[v];
    }
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= m; ++i) {
        if (num[i]) continue;
        pull(i);
    }
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i].first;
        int v = edges[i].second;
        u = comp[u], v = comp[v];
        if (u == v) {
            cout << 'B';
            continue;
        }
        if (u > v) {
            if (w[v] < 0) cout << 'R';
            if (w[v] > 0) cout << 'L';
            if (w[v] == 0) cout << 'B';
        } else {
            if (w[u] < 0) cout << 'L';
            if (w[u] > 0) cout << 'R';
            if (w[u] == 0) cout << 'B';
        }
    }
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < g[u].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < edges.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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