Submission #858924

#	Time	Username	Problem	Language	Result	Execution time	Memory
858924		c2zi6	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	189 ms	37568 KiB

oneway

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define repn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
template<class t> t setmax(t& a, t& b) {if (a < b) return a = b; return a;}
template<class t> t setmin(t& a, t& b) {if (a < b) return a; return a = b;}

const int maxn = 1e5;

int n, m;
vvpi gp, gp2;
vvi comp;
int id[maxn], vis[maxn], num[maxn], low[maxn], bridge[maxn], tc;
int tin[maxn], tout[maxn], par[maxn][20];

void tarjan(int u, int pi = -1) {
    vis[u] = 1;
    low[u] = num[u] = tc++;
    for (auto[v, i] : gp[u]) {
        if (i == pi) continue;
        if (vis[v] == 1) {
            setmin(low[u], num[v]);
        } else if (vis[v] == 0) {
            tarjan(v, i);
            setmin(low[u], low[v]);
            if (low[v] > num[u]) bridge[i] = true;
        }
    }
    vis[u] = 2;
}

int pari[maxn];

void dfs(int u) {
    vis[u] = true;
    comp.back().pb(u);
    for (auto[v, i] : gp[u]) {
        if (vis[v]) continue;
        if (bridge[i]) continue;
        dfs(v);
    }
}

void prelca(int u, int p, int pi = -1) {
    pari[u] = pi;
    vis[u] = true;
    tin[u] = tc++;
    par[u][0] = p;
    for (int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
    for (auto[v, i] : gp2[u]) {
        if (v == p) continue;
        prelca(v, u, i);
    }
    tout[u] = tc++;
}
bool isanc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }
int LCA(int a, int b) {
    if (isanc(a, b)) return a;
    if (isanc(b, a)) return b;
    for (int i = 19; i >= 0; i--) {
        if (!isanc(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}


int ver[maxn], var[maxn];
void dfs2(int u, int p = -1) {
    vis[u] = true;
    for (auto[v, i] : gp2[u]) {
        if (v == p) continue;
        dfs2(v, u);
        ver[u] += ver[v];
        var[u] += var[v];
    }
}

void solve() {
    cin >> n >> m;
    gp = vvpi(n);
    vpi edg;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edg.pb({u, v});
        gp[u].pb({v, i});
        gp[v].pb({u, i});
    }
    fill(vis, vis+n, 0);
    fill(bridge, bridge+m, 0);
    tc = 0;
    for (int u = 0; u < n; u++) {
        if (!vis[u]) tarjan(u);
    }
    comp.clear();
    fill(vis, vis+n, 0);
    for (int u = 0; u < n; u++) {
        if (!vis[u]) {
            comp.pb(vi());
            dfs(u);
        }
    }
    int last = 0;
    for (vi v : comp) {
        for (int x : v) {
            id[x] = last;
        }
        last++;
    }
    gp2 = vvpi(n);
    for (int i = 0; i < m; i++) {
        if (bridge[i]) {
            int u = id[edg[i].ff];
            int v = id[edg[i].ss];
            gp2[u].pb({v, i});
            gp2[v].pb({u, i});
        }
    }
    
    tc = 0;
    fill(vis, vis+n, 0);
    for (int u = 0; u < n; u++) {
        if (!vis[u]) prelca(u, u);
    }
    
    // for (int u = 0; u < last; u++) {
    //     cout << u+1 << ": ";
    //     for (auto[x, i] : gp2[u]) cout << x+1 << " ";
    //     cout << endl;
    // }
    fill(ver, ver+n, 0);
    fill(var, var+n, 0);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a = id[a];
        b = id[b];
        int lca = LCA(a, b);
        // cout << a+1 << " " << b+1 << " " << lca+1 << endl;
        ver[a]++;
        ver[lca]--;
        var[b]++;
        var[lca]--;
    }
    fill(vis, vis+n, 0);
    for (int u = 0; u < n; u++) {
        if (!vis[u]) dfs2(u);
    }
    string ans(m, 'B');
    for (int u = 1; u < n; u++) {
        int i = pari[u];
        int p = par[u][0];
        if (ver[u]) {
            // cout << u+1 << " " << p+1 << endl;
            if (pii{u, p} == pii{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
            else ans[i] = 'L';
        } else if (var[u]) {
            // cout << p+1 << " " << u+1 << endl;
            if (pii{p, u} == pii{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
            else ans[i] = 'L';
        }
    }
    cout << ans << endl;
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(null);
    // cout.tie(null);
    // freopen("milkorder.out", "w", stdout);
    // freopen("milkorder.in", "r", stdin);
    ll t = 1;
    // scanf("%d", &t);
    while (t--) solve();
}

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for (auto[v, i] : gp[u]) {
      |              ^
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for (auto[v, i] : gp[u]) {
      |              ^
oneway.cpp: In function 'void prelca(int, int, int)':
oneway.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto[v, i] : gp2[u]) {
      |              ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for (auto[v, i] : gp2[u]) {
      |              ^

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