제출 #1257066

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

oneway

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

#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl

typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int, int> pii;

const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const double PI = 2 * acos(0.0);

const int N = 1e5 + 5;

int n,m,p,a,b;
int visited[N];;
int low[N],in[N],out[N];
int timer;
vector <vii> v(N),v1(N);
vector <pii> roads;
int up[N][20];
map <pii,bool> isbridge;
map <pii,chr> ans;
int id;
vii lst;
int comp[N];
int l;
vector <pii> newroads;

void dfs1(int x, int p) {
    visited[x] = true;
    in[x] = low[x] = timer++;
    for (auto to:v[x]) {
        if (to == p) continue;
        if (visited[to]) {
            low[x] = min(low[x],in[to]);
        } else {
            dfs1(to,x);
            low[x] = min(low[x],low[to]);
            if (low[to] > in[x]) {
                isbridge[{x,to}] = isbridge[{to,x}] = true;
                v1[to].pb(x);
                v1[x].pb(to);
                newroads.pb({x,to});
            }
        }
    }
}

void dfs2(int x) {
    lst.pb(x);
    visited[x] = true;
    for (auto to:v[x]) {
        if (visited[to]) continue;
        if (isbridge[{to,x}]) continue;
        dfs2(to);
    }
}

void dfs3(int x, int p) {
    in[x] = timer++;
    up[x][0] = p;
    visited[x] = true;
    for (int i = 1; i <= 17; i++) {
        up[x][i] = up[up[x][i-1]][i-1];
    }
    for (auto to:v[x]) {
        if (to == p) continue;
        dfs3(to,x);
    }
    out[x] = timer++;
}

bool ispar(int a, int b) {
    return (in[a] < in[b] && out[a] > out[b]);
}

int lca(int a, int b) {
    if (ispar(a,b)) return a;
    if (ispar(b,a)) return b;
    for (int i = 17; i >= 0; i--) {
        if (!ispar(up[a][i],b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

inline void test_case() {

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
        roads.pb({a,b});
        ans[{a,b}] = 'B';
        ans[{b,a}] = 'B';
    }
    for (int i = 0; i <= n; i++) {
        low[i] = inf;
    }
    for (int i = 1; i <= n; i++) { 
        if (visited[i]) continue;
        dfs1(i,i);
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    id = n+1;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        lst.clear();
        dfs2(i);
        if (sz(lst) > 1) {
            for (auto x:lst) {
                comp[x] = id;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    for (auto [a,b] :roads) {
        if (!isbridge[{a,b}]) {
            if (comp[a]) {
                v1[a].pb(comp[a]);
                v1[comp[a]].pb(a);
                newroads.pb({a,comp[a]});
            }
            if (comp[b]) {
                v1[b].pb(comp[b]);
                v1[comp[b]].pb(b);
                newroads.pb({b,comp[b]});
            }
        }
    }
    v = v1;
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        dfs3(i,i);
        // deb(i);
    }
    cin >> p;
    while (p--) {
        cin >> a >> b;
        l = lca(a,b);
        // cout << "---> " << l << endl;
        while (a != l) {
            int x = up[a][0];
            if (ans[{a,x}] == 'L' || ans[{a,x}] == 'R') break;
            if (ans[{a,x}] == 'R' || ans[{a,x}] == 'L') break;
            ans[{a,x}] = 'R';
            ans[{x,a}] = 'L';
        }
        while (b != l) {
            int x = up[b][0];
            if (ans[{b,x}] == 'L' || ans[{x,b}] == 'L') break;
            if (ans[{b,x}] == 'R' || ans[{x,b}] == 'R') break;
            ans[{x,b}] = 'R';
            ans[{b,x}] = 'L';
        }
    }
    for (auto [a,b]:roads) {
        cout << ans[{a,b}];
    }    
    // cout << endl;
    // for (auto [a,b]:roads) {
    //     cout << isbridge[{a,b}] << endl;
    // }
    // cout << endl;
    // for (auto [a,b]:newroads) {
    //     cout << a<< " " <<b << endl;
    // }


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

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