Submission #1005491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005491		serifefedartar	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	10584 KiB

oneway

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 100;

vector<vector<int>> graph, G, G2;
int mark[MAXN], a[MAXN], b[MAXN], vis[MAXN], par[MAXN], sz[MAXN], ways[MAXN];
int up[LOGN][MAXN], depth[MAXN];

void dfs(int node, int parent) {
    vis[node] = 1;
    for (auto u : graph[node]) {
        if (u != parent && vis[u] != 2)
            G[node].push_back(u);
        if (!vis[u])
            dfs(u, node);
    }
    vis[node] = 2;
}

int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
}

stack<int> nds;
void dfs2(int node) {
    vis[node] = true;
    nds.push(node);
    for (auto u : G[node]) {
        if (vis[u] == 0)
            dfs2(u);
    }
}

void dfs3(int node) {
    vis[node] = true;
    for (auto u : G[node]) {
        if (vis[u])
            continue;
        unite(node, u);
        dfs3(u);
    }
}

void prep(int node, int parent) {
    for (auto u : G2[node]) {
        if (u != parent) {
            up[0][u] = node;
            depth[u] = depth[node] + 1;
            for (int i = 1; i < LOGN; i++)
                up[i][u] = up[i-1][up[i-1][u]];
        }
    }
}

int lift(int node, int k) {
    for (int i = 0; i < LOGN; i++) {
        if ((1<<i) & k)
            node = up[i][node];
    }
    return node;
}

int lca(int a, int b) {
    if (depth[b] > depth[a])
        swap(a, b);
    a = lift(a, depth[a] - depth[b]);
    if (a == b)
        return a;
    for (int i = LOGN-1; i >= 0; i--) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

map<pair<int,int>,int> mp;
int dfs4(int node, int parent) {
    for (auto u : G2[node]) {
        if (u == parent)
            continue;
        dfs4(u, node);
        mark[node] += mark[u];
        if (mark[u]) { // edge : u -> node
            if (mp[{u, node}] == 0)
                ways[mp[{node, u}]] = 1;
            else
                ways[mp[{u, node}]] = 2;
        } else { // edge : node -> u
            if (mp[{u, node}] == 0)
                ways[mp[{node, u}]] = 2;
            else
                ways[mp[{u, node}]] = 1;
        }
    }
    return mark[node];
}

int main() {
    fast
    int n, m, q;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        par[i] = i, sz[i] = 1;
    graph = vector<vector<int>>(n+1, vector<int>());
    G = vector<vector<int>>(n+1, vector<int>());
    G2 = vector<vector<int>>(n+1, vector<int>());
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    dfs2(1);
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    while (nds.size()) {
        int node = nds.top();
        nds.pop();
        if (!vis[node])
            dfs3(node);
    }
    for (int i = 1; i <= m; i++)
        mp[{find(a[i]), find(b[i])}] = i;

    for (int i = 1; i <= m; i++) {
        if (find(a[i]) == find(b[i]))
            ways[i] = -1;
        else {
            G2[find(a[i])].push_back(find(b[i]));
            G2[find(b[i])].push_back(find(a[i]));
        }
    }
    for (int i = 0; i < LOGN; i++)
        up[i][find(1)] = 1;
    prep(find(1), find(1));

    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a == b)
            continue;
        mark[a] += 1;
        mark[lca(a, b)] += -1;
    }
    dfs4(find(1), find(1));

    for (int i = 1; i <= m; i++) {
        if (ways[i] == -1)
            cout << "B";
        else if (ways[i] == 1)
            cout << "L";
        else if (ways[i] == 2)
            cout << "R";
        else
            cout << "B";
    }
    cout << "\n";
}

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