oj.uz

Submission #1081340

# Submission time Handle Problem Language Result Execution time Memory
1081340 2024-08-30T00:06:57 Z PanosPask One-Way Streets (CEOI17_oneway) C++14
100 / 100
 94 ms 22212 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef pair<int, int> pi;

const int MAXUP = 20;

int N, M, P;
vector<vector<int>> adj_list;
vector<pi> edges;
vector<bool> visited;

/* dp[node]:
 * Number of back edges between node and par[node]
 */
vector<int> dp;

vector<vector<int>> ancestor;
vector<int> dep;

vector<int> upwards, downwards;

void dfs(int node, int par)
{
    ancestor[0][node] = par;
    dp[node] = 0;

    for (auto neigh : adj_list[node]) {
        if (neigh == par) {
            par = -1;
            continue;
        }
        else if (dep[neigh] == -1) {
            dep[neigh] = dep[node] + 1;
            dfs(neigh, node);
            dp[node] += dp[neigh];
        }
        else {
            // This is a back edge
            if (dep[neigh] < dep[node]) {
                dp[node]++;
            }
            else if (dep[neigh] > dep[node]) {
                dp[node]--;
            }
        }
    }
}

void propagate(int node, int par)
{
    visited[node] = true;

    for (auto neigh : adj_list[node]) {
        if (dep[neigh] == dep[node] + 1 && !visited[neigh]) {
            propagate(neigh, node);
            upwards[node] += upwards[neigh];
            downwards[node] += downwards[neigh];
        }
    }
}

int jump(int a, int v)
{
    for (int up = 0; up < MAXUP; up++) {
        if (v & (1 << up)) {
            a = ancestor[up][a];
        }
    }

    return a;
}

int lca(int a, int b)
{
    if (dep[a] < dep[b]) {
        swap(a, b);
    }

    a = jump(a, dep[a] - dep[b]);
    if (a == b) {
        return a;
    }

    for (int up = MAXUP - 1; up >= 0; up--) {
        int n_a = ancestor[up][a];
        int n_b = ancestor[up][b];

        if (n_a != n_b) {
            a = n_a;
            b = n_b;
        }
    }

    return ancestor[0][a];
}

void precalculate(void)
{
    for (int up = 1; up < MAXUP; up++) {
        for (int i = 0; i < N; i++) {
            ancestor[up][i] = ancestor[up - 1][ancestor[up - 1][i]];
        }
    }
}

int main(void)
{
    scanf("%d %d", &N, &M);

    adj_list.resize(N);
    ancestor.resize(MAXUP, vector<int>(N));
    dep.assign(N, -1);
    upwards.assign(N, 0);
    downwards.assign(N, 0);
    dp.resize(N);
    visited.assign(N, false);

    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;

        adj_list[u].pb(v);
        adj_list[v].pb(u);
        edges.pb(mp(u, v));
    }

    for (int i = 0; i < N; i++) {
        if (dep[i] == -1) {
            dep[i] = 0;
            dfs(i, i);
        }
    }
    precalculate();

    scanf("%d", &P);
    for (int i = 0; i < P; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;

        int l = lca(u, v);

        upwards[u]++;
        downwards[v]++;
        upwards[l]--;
        downwards[l]--;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i])
            propagate(i, i);
    }

    for (auto [u, v] : edges) {
        int swaped = 0;
        if (dep[u] > dep[v]) {
            swap(u, v);
            swaped = 1;
        }


        if (dep[v] != dep[u] + 1 || dp[v] != 0) {
            printf("B");
        }
        else {
            if (upwards[v] == 0 && downwards[v] == 0) {
                printf("B");
            }
            else {
                assert(upwards[v] == 0 || downwards[v] == 0);
                if ((upwards[v] != 0) ^ swaped) { 
                    printf("L");
                }
                else {
                    printf("R");
                }
            }
        }
    }
    printf("\n");
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:159:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |     for (auto [u, v] : edges) {
      |               ^
oneway.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d", &P);
      |     ~~~~~^~~~~~~~~~
oneway.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 29 ms 6864 KB Output is correct
12 Correct 32 ms 8900 KB Output is correct
13 Correct 39 ms 12064 KB Output is correct
14 Correct 53 ms 16144 KB Output is correct
15 Correct 49 ms 17392 KB Output is correct
16 Correct 44 ms 17352 KB Output is correct
17 Correct 41 ms 18668 KB Output is correct
18 Correct 43 ms 17352 KB Output is correct
19 Correct 42 ms 19652 KB Output is correct
20 Correct 37 ms 11096 KB Output is correct
21 Correct 35 ms 10936 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 29 ms 6864 KB Output is correct
12 Correct 32 ms 8900 KB Output is correct
13 Correct 39 ms 12064 KB Output is correct
14 Correct 53 ms 16144 KB Output is correct
15 Correct 49 ms 17392 KB Output is correct
16 Correct 44 ms 17352 KB Output is correct
17 Correct 41 ms 18668 KB Output is correct
18 Correct 43 ms 17352 KB Output is correct
19 Correct 42 ms 19652 KB Output is correct
20 Correct 37 ms 11096 KB Output is correct
21 Correct 35 ms 10936 KB Output is correct
22 Correct 94 ms 19656 KB Output is correct
23 Correct 83 ms 18376 KB Output is correct
24 Correct 74 ms 18632 KB Output is correct
25 Correct 90 ms 22212 KB Output is correct
26 Correct 89 ms 19400 KB Output is correct
27 Correct 88 ms 18584 KB Output is correct
28 Correct 28 ms 3520 KB Output is correct
29 Correct 87 ms 11852 KB Output is correct
30 Correct 73 ms 12168 KB Output is correct
31 Correct 79 ms 12368 KB Output is correct
32 Correct 71 ms 15436 KB Output is correct