Submission #1081340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081340		PanosPask	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	94 ms	22212 KiB

oneway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40