oj.uz

Submission #858924

# Submission time Handle Problem Language Result Execution time Memory
858924 2023-10-09T11:59:52 Z c2zi6 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 189 ms 37568 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 51 ms 13740 KB Output is correct
12 Correct 57 ms 15300 KB Output is correct
13 Correct 64 ms 19720 KB Output is correct
14 Correct 109 ms 25808 KB Output is correct
15 Correct 102 ms 27332 KB Output is correct
16 Correct 103 ms 32108 KB Output is correct
17 Correct 118 ms 33184 KB Output is correct
18 Correct 117 ms 32076 KB Output is correct
19 Correct 106 ms 34240 KB Output is correct
20 Correct 60 ms 18120 KB Output is correct
21 Correct 58 ms 17856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 51 ms 13740 KB Output is correct
12 Correct 57 ms 15300 KB Output is correct
13 Correct 64 ms 19720 KB Output is correct
14 Correct 109 ms 25808 KB Output is correct
15 Correct 102 ms 27332 KB Output is correct
16 Correct 103 ms 32108 KB Output is correct
17 Correct 118 ms 33184 KB Output is correct
18 Correct 117 ms 32076 KB Output is correct
19 Correct 106 ms 34240 KB Output is correct
20 Correct 60 ms 18120 KB Output is correct
21 Correct 58 ms 17856 KB Output is correct
22 Correct 171 ms 34748 KB Output is correct
23 Correct 176 ms 32896 KB Output is correct
24 Correct 174 ms 32912 KB Output is correct
25 Correct 189 ms 37568 KB Output is correct
26 Correct 175 ms 33984 KB Output is correct
27 Correct 162 ms 32916 KB Output is correct
28 Correct 57 ms 8652 KB Output is correct
29 Correct 107 ms 18848 KB Output is correct
30 Correct 102 ms 18884 KB Output is correct
31 Correct 102 ms 19396 KB Output is correct
32 Correct 120 ms 24056 KB Output is correct