Submission #860172

#	Time	Username	Problem	Language	Result	Execution time	Memory
860172		Nhoksocqt1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	113 ms	29532 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

struct Edge {
    int u, v;
} edge[MAXN];

vector<ii> adj[MAXN];
vector<int> adjp[MAXN];
ii sortedDepth[MAXN];
int cnt[MAXN][2], depth[MAXN], P[MAXN][17];
int low[MAXN], num[MAXN], compID[MAXN], numNode, numComp, numEdge, numPath;
bool dx[MAXN];

stack<int> st;
void dfs(int u) {
    low[u] = num[u] = ++num[0];
    st.push(u);

    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), id(adj[u][it].se);
        if(!dx[id]) {
            dx[id] = 1;
            if(!num[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], num[v]);
            }
        }
    }

    if(low[u] == num[u]) {
        ++numComp;
        int v;
        do {
            v = st.top(); st.pop();
            low[v] = num[v] = 1e9+7;
            compID[v] = numComp;
        } while(v != u);
    }
}

void dfsTree(int u) {
    num[u] = num[0];
    for (int it = 0; it < sz(adjp[u]); ++it) {
        int v(adjp[u][it]);
        if(!num[v]) {
            depth[v] = depth[u] + 1;
            P[v][0] = u;
            dfsTree(v);
        }
    }
}

int lca(int u, int v) {
    if(depth[u] < depth[v])
        swap(u, v);

    for (int i1 = depth[u] - depth[v]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        u = P[u][i];
    }

    if(u == v)
        return u;

    for (int i = 31 - __builtin_clz(depth[u]); i >= 0; --i) {
        if(P[u][i] != P[v][i])
            u = P[u][i], v = P[v][i];
    }

    return P[u][0];
}

void process(void) {
    cin >> numNode >> numEdge;
    for (int i = 0; i < numEdge; ++i) {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int i = 1; i <= numNode; ++i) {
        if(!num[i])
            dfs(i);
    }

    for (int i = 1; i <= numNode; ++i) {
        for (int it = 0; it < sz(adj[i]); ++it) {
            int j(adj[i][it].fi), id(adj[i][it].se);
            if(compID[i] != compID[j]) {
                adjp[compID[i]].push_back(compID[j]);
            }
        }
    }

    for (int i = 1; i <= numComp; ++i)
        num[i] = 0;

    for (int i = 1; i <= numComp; ++i) {
        if(!num[i]) {
            ++num[0];
            depth[i] = 1, P[i][0] = -1;
            dfsTree(i);
        }
    }

    for (int j = 1; (1 << j) <= numComp; ++j) {
        for (int i = 1; i <= numComp; ++i) {
            if(P[i][j - 1] != -1) {
                P[i][j] = P[P[i][j - 1]][j - 1];
            } else {
                P[i][j] = -1;
            }
        }
    }

    cin >> numPath;
    for (int i = 0; i < numPath; ++i) {
        int u, v;
        cin >> u >> v;
        u = compID[u], v = compID[v];

        assert(num[u] == num[v]);
        int par = lca(u, v);

        ++cnt[u][0], ++cnt[v][1];
        --cnt[par][0], --cnt[par][1];
    }

    for (int i = 1; i <= numComp; ++i)
        sortedDepth[i] = {depth[i], i};

    sort(sortedDepth + 1, sortedDepth + numComp + 1);
    for (int i = numComp; i > 0; --i) {
        int u(sortedDepth[i].se);
        if(P[u][0] != -1) {
            cnt[P[u][0]][0] += cnt[u][0];
            cnt[P[u][0]][1] += cnt[u][1];
        }
    }

    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);
        u = compID[u], v = compID[v];
        if(u == v) {
            cout << 'B';
        } else {
            bool isSwapped(0);

            if(P[u][0] == v) {
                swap(u, v);
                isSwapped = 1;
            }

            //cout << '.' << edge[i].u << ' ' << edge[i].v << ' ' << u << ' ' << v << ' ' << cnt[v][0] << ' ' << cnt[v][1] << '\n';
            if(cnt[v][0] && cnt[v][1] || !cnt[v][0] && !cnt[v][1]) {
                cout << 'B';
            } else {
                cout << (((cnt[v][1] > 0) ^ isSwapped) ? 'R' : 'L');
            }
        }
    }

    cout << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    process();
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void process()':
oneway.cpp:107:35: warning: unused variable 'id' [-Wunused-variable]
  107 |             int j(adj[i][it].fi), id(adj[i][it].se);
      |                                   ^~
oneway.cpp:174:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  174 |             if(cnt[v][0] && cnt[v][1] || !cnt[v][0] && !cnt[v][1]) {
      |                ~~~~~~~~~~^~~~~~~~~~~~

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