oj.uz

Submission #1011249

# Submission time Handle Problem Language Result Execution time Memory
1011249 2024-06-30T07:54:29 Z voi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 119 ms 46420 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];

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;
        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 upp[ar], down[ar];

void dfs3(int u) {
    vs[u] = 1;
    for(auto &[v, i, t] : adj[u]) if(!vs[v]) {
        dfs3(v);
        if(upp[v] && down[v] == 0) val[i] = t ^ 1;
        else if(down[v] && upp[v] == 0) val[i] = t;
//        cout << upp[v] << ' ' << down[v] << '\n';
        upp[u] += upp[v];
        down[u] += down[v];
    }
}
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(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';
        upp[u]++; upp[p]--;
        down[v]++; down[p]--;
//        cout << "end\n";
    }

    memset(vs, 0, sizeof vs);
    for(int i = 1; i <= scc; ++i) if(!vs[i])
        dfs3(i);
    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] == 1) cout << 'L';
        else cout << 'R';
//        cout << '\n';
    }
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 7 ms 22876 KB Output is correct
3 Correct 8 ms 22968 KB Output is correct
4 Correct 7 ms 23128 KB Output is correct
5 Correct 8 ms 23168 KB Output is correct
6 Correct 6 ms 22872 KB Output is correct
7 Correct 8 ms 23132 KB Output is correct
8 Correct 7 ms 23292 KB Output is correct
9 Correct 7 ms 22876 KB Output is correct
10 Correct 7 ms 22940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 7 ms 22876 KB Output is correct
3 Correct 8 ms 22968 KB Output is correct
4 Correct 7 ms 23128 KB Output is correct
5 Correct 8 ms 23168 KB Output is correct
6 Correct 6 ms 22872 KB Output is correct
7 Correct 8 ms 23132 KB Output is correct
8 Correct 7 ms 23292 KB Output is correct
9 Correct 7 ms 22876 KB Output is correct
10 Correct 7 ms 22940 KB Output is correct
11 Correct 31 ms 29276 KB Output is correct
12 Correct 35 ms 30148 KB Output is correct
13 Correct 41 ms 31352 KB Output is correct
14 Correct 46 ms 33872 KB Output is correct
15 Correct 49 ms 35216 KB Output is correct
16 Correct 65 ms 41300 KB Output is correct
17 Correct 68 ms 42340 KB Output is correct
18 Correct 77 ms 41152 KB Output is correct
19 Correct 71 ms 43504 KB Output is correct
20 Correct 44 ms 29404 KB Output is correct
21 Correct 31 ms 29268 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 7 ms 22876 KB Output is correct
3 Correct 8 ms 22968 KB Output is correct
4 Correct 7 ms 23128 KB Output is correct
5 Correct 8 ms 23168 KB Output is correct
6 Correct 6 ms 22872 KB Output is correct
7 Correct 8 ms 23132 KB Output is correct
8 Correct 7 ms 23292 KB Output is correct
9 Correct 7 ms 22876 KB Output is correct
10 Correct 7 ms 22940 KB Output is correct
11 Correct 31 ms 29276 KB Output is correct
12 Correct 35 ms 30148 KB Output is correct
13 Correct 41 ms 31352 KB Output is correct
14 Correct 46 ms 33872 KB Output is correct
15 Correct 49 ms 35216 KB Output is correct
16 Correct 65 ms 41300 KB Output is correct
17 Correct 68 ms 42340 KB Output is correct
18 Correct 77 ms 41152 KB Output is correct
19 Correct 71 ms 43504 KB Output is correct
20 Correct 44 ms 29404 KB Output is correct
21 Correct 31 ms 29268 KB Output is correct
22 Correct 105 ms 43600 KB Output is correct
23 Correct 97 ms 42064 KB Output is correct
24 Correct 83 ms 42312 KB Output is correct
25 Correct 119 ms 46420 KB Output is correct
26 Correct 106 ms 43276 KB Output is correct
27 Correct 99 ms 42068 KB Output is correct
28 Correct 29 ms 27220 KB Output is correct
29 Correct 45 ms 30112 KB Output is correct
30 Correct 56 ms 30288 KB Output is correct
31 Correct 45 ms 30544 KB Output is correct
32 Correct 74 ms 35412 KB Output is correct