Submission #918358

#	Time	Username	Problem	Language	Result	Execution time	Memory
918358		habel	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define INF (LLONG_MAX/2)
#pragma GCC optimize ("O3")

vector<vector<pair<int, int> > > g, g2;
vector<int> tin, l, comp;
vector<char> elirany; 
int t = 1;
int mincomp=1; 
void dfs(int v, int p = -1) {
    tin[v] = t++;
    l[v] = tin[v];
    for (auto [u, i] : g[v]) {
        if (u != p) {
            if (!tin[u]) {
                comp[u]=comp[v];
                dfs(u, v);
                l[v] = min(l[v], l[u]);
                if (l[u] > tin[v]) {
                    mincomp++;
                    comp[u]=mincomp;
                    g2[comp[v]].push_back(make_pair(comp[u], i));
                    g2[comp[u]].push_back(make_pair(comp[v], -i));
                }
            } else {
                l[v] = min(l[v], tin[u]);
            }
        }
    }
}

bool dfs2(int v, int cel, int p=-1) {
    if (cel == v) return true;
    for (auto [u, i] : g2[v]) {
        if (u == p) continue;
        if (dfs2(u, cel, v)) {
            if (i > 0) {
                elirany[i] = 'R';
            } else {
                elirany[-i] = 'L';
            }
            return true;
        }
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    g.resize(n + 1);
    tin.resize(n + 1, 0);
    l.resize(n + 1, INF);
    comp.resize(n + 1);
    elirany.resize(m+1,'B');
    g2.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        
        g[a].push_back({b, i});
        g[b].push_back({a, -i});
    }
    comp[1]=mincomp;
    dfs(1);
    //for (int i=1; i<=n;i++) cout<<comp[i]<<endl; 
    int q;
    cin >> q;
    vector<int> from(q), to(q);
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a = comp[a];
        b = comp[b];
        from[i] = a;
        to[i] = b;
        dfs2(a, b);
    }
    for (int i=1; i<=m;i++){
        cout << elirany[i];
    }
    cout << endl;
}

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