oj.uz

Submission #1081338

# Submission time Handle Problem Language Result Execution time Memory
1081338 2024-08-30T00:01:27 Z PanosPask One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3000 ms 604 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;

/* 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)
{
    for (auto neigh : adj_list[node]) {
        if (dep[neigh] == dep[node] + 1) {
            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);

    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 (dep[i] == 0)
            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:155:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |     for (auto [u, v] : edges) {
      |               ^
oneway.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%d", &P);
      |     ~~~~~^~~~~~~~~~
oneway.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Execution timed out 3063 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Execution timed out 3063 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Execution timed out 3063 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -