제출 #1226124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226124		giorgikob	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	11 ms	23872 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int n, m;
vector<pair<int,int>> gr[N];
int lvl[N], up[N], P[N][20];
int in[N], out[N];
int timer;
int A[N], B[N];

void dfs(int x, int ind, int p) {
    lvl[x] = lvl[p] + 1;

    P[x][0] = p;
    for (int i = 1; i < 20; i++) {
        P[x][i] = P[P[x][i-1]][i-1];
    }
    in[x] = timer++;

    for (auto [to, i] : gr[x]) {
        if (lvl[to] == 0) {
            dfs(to, i, x);
            up[x] += up[to];
        } else {
            if (i == ind) continue;
            if (lvl[to] < lvl[x]) {
                up[x]++;
            } else {
                up[x]--;
            }
        }
    }

    // cout << x << " " << up[x] << endl;

    out[x] = timer;
}

bool check(int x, int y) {
    return in[x] <= in[y] && out[y] <= out[x];
}

int lca(int x, int y) {
    if (check(x, y)) return x;

    for (int i = 19; i >= 0; i--) {
        if (P[x][i] && !check(P[x][i], y)) {
            x = P[x][i];
        }
    }

    return P[x][0];
}

pair<int,int> edge[N];
int fix[N];
char answer[N];

void dfs1(int x, int ind) {
    fix[x] = 1;
    for (auto [to, i] : gr[x]) {
        if (fix[to]) continue;
        dfs1(to, i);
        A[x] += A[to];
        B[x] += B[to];
    }

    if (up[x] == 0 && x != 1) {
        if (A[x] > 0) {
            if (edge[ind] == make_pair(x, P[x][0])) {
                answer[ind] = 'R';
            } else {
                answer[ind] = 'L';
            }
        } else {
            if(edge[ind] == make_pair(x, P[x][0])) {
                answer[ind] = 'L';
            } else {
                answer[ind] = 'R';
            }
        }
    }
}


int main() {

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back({y, i});
        gr[y].push_back({x, i});
        edge[i] = {x, y};
        answer[i] = 'B';
    }

    dfs(1, 0, 0);

    int k;
    cin >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        int z = lca(x, y);
        A[x]++; A[z]--;
        B[y]++; B[z]--;
    }

    dfs1(1, 0);

    for (int i = 0; i < m; i++) {
        cout << answer[i];
    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40