Submission #1006234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006234		LOLOLO	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	122 ms	29268 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 1e3;

int n, m;
bool is[N];
int low[N], num[N], timeDfs = 1;
vector <pair <int, int>> g[N];

void dfs(int u, int pre) {
    num[u] = low[u] = ++timeDfs;
    for (auto x : g[u]) {
        if (x.s == pre) 
            continue;

        if (num[x.f] == 0) {
            dfs(x.f, x.s);
            low[u] = min(low[u], low[x.f]);
            if (low[x.f] == num[x.f]) {
                is[x.s] = 1;
            }
        } else low[u] = min(low[u], num[x.f]);
    }
}

char ans[N];
int u[N], v[N];

struct DSU{
    vector <int> p, sz;
    void ass(int n) {
        p.assign(n + 1, 0);
        sz.assign(n + 1, 1);
    }

    int get(int a) {
        return p[a] ? get(p[a]) : a;
    }

    void unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b)
            return;

        if (sz[a] < sz[b]) 
            swap(a, b);

        sz[a] += sz[b];
        p[b] = a;
    }
};

vector <pair <int, int>> ed[N];
int p[N][20], in[N], ou[N], timer = 1, up[N], down[N], used[N];

void dfs1(int u, int v) {
    p[u][0] = v;
    for (int j = 1; j < 20; j++) 
        p[u][j] = p[p[u][j - 1]][j - 1];

    in[u] = ++timer;
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        dfs1(x.f, u);
    }

    ou[u] = timer;
}

int anc(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b];
}

int lca(int a, int b) {
    if (anc(a, b))
        return a;

    if (anc(b, a))
        return b;

    for (int j = 19; j >= 0; j--) {
        if (anc(p[a][j], b) == 0)
            a = p[a][j];
    }

    return p[a][0];
}

void dfs2(int t, int id) { 
    used[t] = 1;
    if (down[in[t] - 1] != down[ou[t]]) {
        if (v[id] == t) {
            ans[id] = 'R';
        } else {
            ans[id] = 'L';
        }
    }

    if (up[in[t] - 1] != up[ou[t]]) {
        if (u[id] == t) {
            ans[id] = 'R';
        } else {
            ans[id] = 'L';
        }
    }

    for (auto x : ed[t]) {
        if (x.s == id)
            continue;

        dfs2(x.f, x.s);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
    }

    for (int i = 1; i <= n; i++)
        if (!num[i]) 
            dfs(i, 0);

    DSU D;
    D.ass(n + 1);

    for (int i = 1; i <= m; i++) {
        ans[i] = 'B';
        if (is[i] == 0) { 
            D.unite(u[i], v[i]); 
        }
    }

    for (int i = 1; i <= m; i++) {
        if (is[i]) {
            u[i] = D.get(u[i]), v[i] = D.get(v[i]);
            ed[u[i]].pb({v[i], i});
            ed[v[i]].pb({u[i], i});
        }
    }

    for (int i = 1; i <= n; i++) {
        int t = D.get(i);
        if (sz(ed[t]) && in[t] == 0)
            dfs1(t, t);
    }

    int p;
    cin >> p;

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a = D.get(a), b = D.get(b);
        if (a == b)
            continue;

        int c = lca(a, b);
        up[in[a]]++, up[in[c]]--;
        down[in[b]]++, down[in[c]]--;
    }

    for (int i = 1; i < N; i++) {
        up[i] += up[i - 1];
        down[i] += down[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        int t = D.get(i);
        if (used[t] == 0)
            dfs2(t, 0);
    }

    for (int i = 1; i <= m; i++) {
        cout << ans[i];
    }

    cout << '\n';
}

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

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