oj.uz

Submission #1074710

# Submission time Handle Problem Language Result Execution time Memory
1074710 2024-08-25T13:10:05 Z voi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 140 ms 45644 KB 
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define lb(s, a) lower_bound(all(s), (a)) - s.begin()
#define ii pair <int, int>
#define fi first
#define se second

using namespace std;

typedef long long ll;

const int ar = 2e5+2;
const ll mod = 1e9+7;
const int oo = 1e9;

int n, m;
int timeDfs = 0, scc = 0;
int low[ar], num[ar];
int id[ar];
bool vs[ar], bridge[ar];
struct set3 {
    int v, i, t;
    bool operator < (set3 a) {
        return v < a.v;
    }
    bool operator == (set3 a) {
        return v == a.v;
    }
};
vector <set3> g[ar], adj[ar];
stack <int> st;

void dfs(int u, int p) {
    num[u] = low[u] = ++timeDfs;
    for (auto [v, i, t] : g[u]) if(v != p) {
      if (vs[v]) continue;
        if (!num[v]){
            dfs(v, u);
            if(low[v] == num[v]) bridge[i] = 1;
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], num[v]);
    }
}

void cay(int u, int sc) {
    id[u] = sc;
//    cout << u << ' ' << id[u] << ' ' << low[u] << ' ' << num[u] << '\n';
    for(auto [v, i, t] : g[u]) {
        if(id[v] || bridge[i]) continue;
        cay(v, sc);
    }
}

int h[ar], up[ar][18], val[ar];
set3 par[ar];

void dfs2(int u, int p) {
    vs[u] = 1;
    for(auto &[v, i, t] : adj[u]) {
        if(v == p) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        par[v] = {u, i, t};
        for(int j = 1; j < 17; ++j)
            up[v][j] = up[up[v][j - 1]][j - 1];
        dfs2(v, u);
    }
}
int lca(int u, int v) {
    if(h[u] != h[v]) {
        if(h[u] < h[v]) swap(u, v);

        int k = h[u] - h[v];
        for(int j = 0; (1 << j) <= k; ++j)
            if(k >> j & 1)
                u = up[u][j];
    }
    if(u == v) return u;

    int k = 31 - __builtin_clz(h[u]);
    for(int j = k; j >= 0; --j)
    if(up[u][j] != up[v][j]) {
        u = up[u][j];
        v = up[v][j];
    }
    return up[u][0];
}

int lab[ar];

int find_set(int v) {
    return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a != b) {
        lab[b] += lab[a];
        lab[a] = b;
    }
}

void direct(int u, int p, int t) {
    if(u == p) return;
//    cout << p << '\n';
    int pos = p;
    u = find_set(u);
    int goc = u;
    while(h[u] > h[p]) {
//        cout << u << ' ' << par[u].v << '\n';
        val[par[u].i] = par[u].t ^ t;
        u = par[u].v;
        u = find_set(u);
        pos = u;
    }

    u = goc;
    int tmp;
    while(h[u] > h[p]) {
//        cout << u << ' ' << par[u].v << '\n';
        tmp = u;
        u = par[u].v;
        u = find_set(u);
        union_sets(tmp, pos);
    }
//    cout << '\n';
}
vector <int> same[ar], nhom[ar];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "CEOI17_ONEWAY"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    h[0] = -1;
    cin >> n >> m;
    int u, v;
    memset(lab, -1, sizeof lab);
    memset(val, -1, sizeof val);
    for(int i = 1; i <= m; ++i) {
        cin >> u >> v;
        g[u].push_back({v, i, 0});
        g[v].push_back({u, i, 1});
    }
//    for(int i = 1; i <= n; ++i) {
//        sort(all(g[i]));
//        for(int j = 0; j < g[i].size();) {
//            int k = j + 1;
//            while(k < g[i].size() && g[i][j].v == g[i][k].v)
//                same[g[i][j].i].push_back(g[i][k].i), ++k;
//            j = k;
//        }
//        g[i].resize(unique(all(g[i])) - g[i].begin());
//    }
    int dem = 0;
    for(int i = 1; i <= n; ++i) if(num[i] == 0)
        dfs(i, 0);
    for(int i = 1; i <= n; ++i) if(id[i] == 0) {
        scc++;
        cay(i, scc);
    }
//    cout << scc << '\n';
    for(int u = 1; u <= n; ++u)
        for(auto [v, i, t] : g[u]) if(id[u] != id[v])
        adj[id[u]].push_back({id[v], i, t});
    memset(vs, 0, sizeof vs);
    for(int i = 1; i <= n; ++i) if(!vs[id[i]])
        dfs2(id[i], 0);
//    for(int i = 1; i <= n; ++i)
//        nhom[id[i]].push_back(i);
//    for(int i = 1; i <= scc; ++i) {
//        for(auto u : nhom[i]) cout << u << ' '; cout << '\n';
//    }
//    for(int i = 1; i <= scc; ++i)
//        cout << par[i].v << ' ' << h[i] << '\n';
    int q;
    cin >> q;
    while(q--) {
        cin >> u >> v;
        u = id[u]; v = id[v];
        int p = lca(u, v);
//        cout << u << ' ' << v << ' ' << p << '\n';
        direct(u, p, 0);
        direct(v, p, 1);
//        cout << "end\n";
    }

//    memset(vs, 0, sizeof vs);
//    for(int i = 1; i <= scc; ++i) if(!vs[i])
//        dfs3(i, 0);
    for(int i = 1; i <= m; ++i)
        for(auto j : same[i])
        val[j] = val[i];
//    cout << m << '\n';
    for(int i = 1; i <= m; ++i) {
        if(val[i] == -1) cout << 'B';
        else if(val[i] == 0) cout << 'L';
        else cout << 'R';
//        cout << '\n';
    }
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:161:9: warning: unused variable 'dem' [-Wunused-variable]
  161 |     int dem = 0;
      |         ^~~
oneway.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20828 KB Output is correct
2 Correct 9 ms 20828 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 8 ms 21184 KB Output is correct
6 Correct 9 ms 21084 KB Output is correct
7 Correct 12 ms 21260 KB Output is correct
8 Correct 9 ms 21084 KB Output is correct
9 Correct 10 ms 21084 KB Output is correct
10 Correct 10 ms 21084 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20828 KB Output is correct
2 Correct 9 ms 20828 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 8 ms 21184 KB Output is correct
6 Correct 9 ms 21084 KB Output is correct
7 Correct 12 ms 21260 KB Output is correct
8 Correct 9 ms 21084 KB Output is correct
9 Correct 10 ms 21084 KB Output is correct
10 Correct 10 ms 21084 KB Output is correct
11 Correct 34 ms 27452 KB Output is correct
12 Correct 40 ms 28500 KB Output is correct
13 Correct 45 ms 29780 KB Output is correct
14 Correct 55 ms 32600 KB Output is correct
15 Correct 57 ms 34124 KB Output is correct
16 Correct 69 ms 40628 KB Output is correct
17 Correct 76 ms 41700 KB Output is correct
18 Correct 71 ms 40528 KB Output is correct
19 Correct 76 ms 42744 KB Output is correct
20 Correct 42 ms 27644 KB Output is correct
21 Correct 41 ms 27652 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20828 KB Output is correct
2 Correct 9 ms 20828 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 8 ms 21184 KB Output is correct
6 Correct 9 ms 21084 KB Output is correct
7 Correct 12 ms 21260 KB Output is correct
8 Correct 9 ms 21084 KB Output is correct
9 Correct 10 ms 21084 KB Output is correct
10 Correct 10 ms 21084 KB Output is correct
11 Correct 34 ms 27452 KB Output is correct
12 Correct 40 ms 28500 KB Output is correct
13 Correct 45 ms 29780 KB Output is correct
14 Correct 55 ms 32600 KB Output is correct
15 Correct 57 ms 34124 KB Output is correct
16 Correct 69 ms 40628 KB Output is correct
17 Correct 76 ms 41700 KB Output is correct
18 Correct 71 ms 40528 KB Output is correct
19 Correct 76 ms 42744 KB Output is correct
20 Correct 42 ms 27644 KB Output is correct
21 Correct 41 ms 27652 KB Output is correct
22 Correct 140 ms 42920 KB Output is correct
23 Correct 111 ms 41300 KB Output is correct
24 Correct 95 ms 41552 KB Output is correct
25 Correct 115 ms 45644 KB Output is correct
26 Correct 128 ms 42500 KB Output is correct
27 Correct 115 ms 41552 KB Output is correct
28 Correct 27 ms 25436 KB Output is correct
29 Correct 54 ms 28500 KB Output is correct
30 Correct 51 ms 28500 KB Output is correct
31 Correct 50 ms 28756 KB Output is correct
32 Correct 77 ms 34132 KB Output is correct