제출 #533876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533876		alextodoran	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	5068 KiB

oneway

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int n, m;
int eu[N_MAX + 2], ev[N_MAX + 2];
vector <int> adj[N_MAX + 2];

bool seen[N_MAX + 2];
int parent[N_MAX + 2];
int level[N_MAX + 2];
int minAbove[N_MAX + 2];

bool bridge[N_MAX + 2];

void dfs (int u) {
    seen[u] = true;
    minAbove[u] = level[u];
    for (int v : adj[u]) {
        if (seen[v] == false) {
            parent[v] = u;
            level[v] = level[u] + 1;
            dfs(v);
            minAbove[u] = min(minAbove[u], minAbove[v]);
        } else if (v != parent[u]) {
            minAbove[u] = min(minAbove[u], level[v]);
        }
    }
    if (minAbove[u] >= level[u]) {
        bridge[u] = true;
    }
}
void dfs () {
    dfs(1);
}

int DSU[N_MAX + 2];
void DSUinit () {
    for (int u = 1; u <= n; u++) {
        DSU[u] = u;
    }
}
int DSUroot (int u) {
    return (DSU[u] == u ? u : DSU[u] == DSUroot(DSU[u]));
}
void DSUjoin (int u, int v) {
    DSU[DSUroot(u)] = DSUroot(v);
}

vector <int> tree[N_MAX + 2];

int L[N_MAX + 2];
int R[N_MAX + 2];
int curr;

void linearize (int u, int from = -1) {
    L[u] = R[u] = ++curr;
    for (int v : tree[u]) {
        if (v != from) {
            linearize(v, u);
            R[u] = R[v];
        }
    }
}

int k;

int cntok[N_MAX + 2];
void addok (int l, int r) {
    cntok[l]++;
    cntok[r + 1]--;
}

int dist[N_MAX + 2];
void getDist (int root) {
    for (int u = 1; u <= n; u++) {
        dist[u] = -1;
    }
    queue <int> q; q.push(root); dist[root] = 0;
    while (q.empty() == false) {
        int u = q.front(); q.pop();
        for (int v : tree[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        adj[eu[i]].push_back(ev[i]);
        adj[ev[i]].push_back(eu[i]);
    }

    dfs();

    set <pair <int, int>> onlyOne;
    DSUinit();
    for (int u = 2; u <= n; u++) {
        if (bridge[u] == false) {
            DSUjoin(u, parent[u]);
        }
    }
    for (int u = 2; u <= n; u++) {
        if (bridge[u] == true) {
            int x = DSUroot(u), y = DSUroot(parent[u]);
            tree[x].push_back(y);
            tree[y].push_back(x);
            onlyOne.insert(make_pair(u, parent[u]));
            onlyOne.insert(make_pair(parent[u], u));
        }
    }

    linearize(DSUroot(1));

    cin >> k;
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        int x = DSUroot(u), y = DSUroot(v);
        if (x == y) {
            addok(1, n);
        } else if (L[x] <= L[y] && R[y] <= R[x]) {
            addok(1, L[x] - 1);
            addok(R[x] + 1, n);
        } else {
            addok(L[x], R[x]);
        }
    }
    for (int i = 1; i <= n; i++) {
        cntok[i] += cntok[i - 1];
    }

    int root = -1;
    for (int u = 1; u <= n; u++) {
        if (DSU[u] == u && cntok[L[u]] == k) {
            root = u;
            break;
        }
    }

    getDist(root);

    for (int i = 1; i <= m; i++) {
        int u = eu[i], v = ev[i];
        if (onlyOne.find(make_pair(u, v)) == onlyOne.end()) {
            cout << 'B';
        } else {
            cout << (dist[DSUroot(u)] < dist[DSUroot(v)] ? 'R' : 'L');
        }
    }
    cout << "\n";

    return 0;
}

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