Submission #1006356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006356		serifefedartar	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	139 ms	36692 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, G_rev;
vector<vector<pair<int,int>>> G2;
int mark[MAXN], a[MAXN], b[MAXN], vis[MAXN], par[MAXN], sz[MAXN], ways[MAXN];
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];
}

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);
            G_rev[u].push_back(node);
        }
        if (!vis[u])
            dfs(u, node);
    }
    vis[node] = 2;
}

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

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

void dfs4(int node) {
    vis[node] = true;
    for (auto u : G2[node]) {
        if (vis[u.f])
            continue;
        dfs4(u.f);
        mark[node] += mark[u.f];
        if (find(a[u.s]) == node) {
            if (mark[u.f] > 0)
                ways[u.s] = 1;
            else if (mark[u.f] < 0)
                ways[u.s] = 2;
        } else { // b[u.s] == node
            if (mark[u.f] > 0)
                ways[u.s] = 2;
            else if (mark[u.f] < 0)
                ways[u.s] = 1;
        }
    }
}

map<pair<int,int>,int> mp;
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<pair<int,int>>>(n+1, vector<pair<int,int>>());
    G_rev = vector<vector<int>>(n+1, vector<int>());
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        mp[{min(a[i], b[i]), max(a[i], b[i])}]++;
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs(i, i);
    }
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs2(i);
    }
    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++) {
        if (find(a[i]) == find(b[i]))
            ways[i] = -1;
        else {
            G2[find(a[i])].push_back({find(b[i]), i});
            G2[find(b[i])].push_back({find(a[i]), i});
        }
    }

    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a == b)
            continue;

        mark[b] -= 1;
        mark[a] += 1;
    }

    for (int i = 1; i <= n; i++)
        vis[i] = false;
    for (int i = 1; i <= n; i++) {
        if (!vis[find(i)])
            dfs4(find(i));
    }

    for (int i = 1; i <= m; i++) {
        if (mp[{min(a[i], b[i]), max(a[i], b[i])}] > 1 || a[i] == b[i])
            cout << "B";
        else if (ways[i] == 1)
            cout << "L";
        else if (ways[i] == 2)
            cout << "R";
        else
            cout << "B";
    }
    cout << "\n";
}

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