oj.uz

Submission #1011252

# Submission time Handle Problem Language Result Execution time Memory
1011252 2024-06-30T08:08:55 Z voi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 69 ms 27220 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;
};
vector <set3> g[ar], adj[ar];

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 val[ar];
int cnt[ar];

void dfs3(int u, int p) {
    vs[u] = 1;
    for(auto &[v, i, t] : adj[u]) {
        if(v == p) continue;
        dfs3(v, u);
        if(cnt[v] < 0) val[i] = t ^ 1;
        else if(cnt[v] > 0) val[i] = t;
        cnt[u] += cnt[v];
    }
}

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);
    }

    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});
    }
    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);
    }
    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});
    int q;
    cin >> q;
    while(q--) {
        cin >> u >> v;
        u = id[u]; v = id[v];
        cnt[u]++;
        cnt[v]--;
    }

    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) {
        if(val[i] == -1) cout << 'B';
        else if(val[i] == 0) cout << 'L';
        else cout << 'R';
    }
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10844 KB Output is correct
2 Correct 4 ms 10792 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 5 ms 10844 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10844 KB Output is correct
2 Correct 4 ms 10792 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 5 ms 10844 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 34 ms 17232 KB Output is correct
12 Correct 32 ms 18264 KB Output is correct
13 Correct 36 ms 19284 KB Output is correct
14 Correct 43 ms 20304 KB Output is correct
15 Correct 43 ms 20624 KB Output is correct
16 Correct 45 ms 22108 KB Output is correct
17 Correct 46 ms 23380 KB Output is correct
18 Correct 50 ms 22100 KB Output is correct
19 Correct 46 ms 24400 KB Output is correct
20 Correct 31 ms 17500 KB Output is correct
21 Correct 29 ms 17240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10844 KB Output is correct
2 Correct 4 ms 10792 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 5 ms 10844 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 34 ms 17232 KB Output is correct
12 Correct 32 ms 18264 KB Output is correct
13 Correct 36 ms 19284 KB Output is correct
14 Correct 43 ms 20304 KB Output is correct
15 Correct 43 ms 20624 KB Output is correct
16 Correct 45 ms 22108 KB Output is correct
17 Correct 46 ms 23380 KB Output is correct
18 Correct 50 ms 22100 KB Output is correct
19 Correct 46 ms 24400 KB Output is correct
20 Correct 31 ms 17500 KB Output is correct
21 Correct 29 ms 17240 KB Output is correct
22 Correct 69 ms 24368 KB Output is correct
23 Correct 69 ms 22912 KB Output is correct
24 Correct 60 ms 23376 KB Output is correct
25 Correct 59 ms 27220 KB Output is correct
26 Correct 65 ms 24156 KB Output is correct
27 Correct 62 ms 23096 KB Output is correct
28 Correct 32 ms 15184 KB Output is correct
29 Correct 46 ms 18256 KB Output is correct
30 Correct 47 ms 18512 KB Output is correct
31 Correct 44 ms 18524 KB Output is correct
32 Correct 49 ms 21588 KB Output is correct