Submission #1296925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296925		khoile08	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	104 ms	29408 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 2;

int n, m, q;
vector<ii> g[N];
ii ed[N];
int ans[N];

int times, scc;
int low[N], num[N], used[N], del[N];
stack<int> st;

vector<iii> ng[N];
ii idx[N];
int par[18][N], vis[N], dp1[N], dp2[N], h[N];

void dfs(int u) {
    st.push(u);
    low[u] = num[u] = ++times;
    for(auto H : g[u]) {
        int v = H.fi;
        int id = H.se;
        if(used[id] || del[v]) continue;
        used[id] = 1;
        if(!num[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], num[v]);
    }
    if(low[u] == num[u]) {
        int v;
        scc++;
        do {
            v = st.top();
            st.pop();
            del[v] = scc;
        }
        while(u != v);
    }
}

void dfs2(int u, int p) {
    par[0][u] = p;
    for(auto H : ng[u]) {
        int v = H.fi;
        if(v == p) continue;
        h[v] = h[u] + 1;
        idx[v] = H.se;
        dfs2(v, u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    int dif = h[u] - h[v];
    FOD(i, 17, 0) if((dif >> i) & 1) u = par[i][u];
    if(u == v) return u;
    FOD(i, 17, 0) {
        if(par[i][u] != par[i][v]) {
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

void dfs3(int u, int p) {
    vis[u] = 1;
    for(auto H : ng[u]) {
        int v = H.fi;
        if(v == p) continue;
        dfs3(v, u);
        dp1[u] += dp1[v];
        dp2[u] += dp2[v];
    }
}

void Solve() {
    FOR(i, 1, n) if(!num[i]) dfs(i);
    FOR(i, 1, m) {
        int u = del[ed[i].fi];
        int v = del[ed[i].se];
        if(u != v) {
            ng[u].pb({v, {i, 0}});
            ng[v].pb({u, {i, 1}});
        }
    }

    FOR(i, 1, scc) if(par[0][i] == 0) dfs2(i, -1);
    FOR(i, 1, 17) FOR(j, 1, n) par[i][j] = par[i - 1][par[i - 1][j]];

    cin >> q;
    FOR(i, 1, q) {
        int u, v;
        cin >> u >> v;
        u = del[u];
        v = del[v];
        if(u == v) continue;
        int p = lca(u, v);
        dp1[u]++;
        dp2[v]++;
        dp1[p]--;
        dp2[p]--;
    }
    FOR(i, 1, scc) if(!vis[i]) dfs3(i, -1);
    FOR(i, 1, scc) {
        if(dp1[i]) {
            if(idx[i].se == 0) ans[idx[i].fi] = 2;
            else ans[idx[i].fi] = 1;
        }
        else if(dp2[i]) {
            if(idx[i].se) ans[idx[i].fi] = 2;
            else ans[idx[i].fi] = 1;
        }
    }

    FOR(i, 1, m) {
        if(ans[i] == 0) cout << 'B';
        else if(ans[i] == 1) cout << 'R';
        else cout << 'L';
    }
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n >> m;
        FOR(i, 1, m) {
            int u, v;
            cin >> u >> v;
            g[u].pb({v, i});
            g[v].pb({u, i});
            ed[i] = {u, v};
        }
        Solve();
    }
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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