Submission #1259709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259709		sitingfake	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	61 ms	20036 KiB

oneway

#include <bits/stdc++.h>

#define name "way"
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
#define ll long long
#define fi first
#define se second
#define ii pair <int, int>
#define sz(a) (int) a.size()
#define pb push_back
#define MASK(x) (1ll << x)
#define bit(x, i) ((x >> i) & 1)
#define pop_count(x) __builtin_popcount(x)
#define mingdu signed main()

using namespace std;

const ll mod = 1e9 + 7;

void add(ll& a, ll b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<class X, class Y> void mx(X &x, const Y y) {if (y > x) x = y;}
template<class X, class Y> void mn(X &x, const Y y) {if (y < x) x = y;}

const int N = 1e5 + 5;
int a[N], n, m, tin[N], low[N], timer;
int scc[N], cnt;
char ans[N];
ll diff[N];
bool d[N], vis[N];
vector <ii> adj[N], g[N];
ii edge[N];

void nhap() {
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v; cin >> u >> v;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
        edge[i] = {u, v};
    }
}

void dfs(int u, int p) {
    tin[u] = low[u] = ++timer;
    FOR(i, 0, sz(adj[u]) - 1) {
        int v = adj[u][i].fi;
        int id = adj[u][i].se;
        if (id == p) continue;

        if (!tin[v]) {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) d[id] = 1;
        }

        else low[u] = min(low[u], tin[v]);
    }
}

void dfs_scc(int u) {
    scc[u] = cnt;
    FOR(i, 0, sz(adj[u]) - 1) {
        int v = adj[u][i].fi;
        int id = adj[u][i].se;
        if (!d[id] && !scc[v]) dfs_scc(v);
    }
}

ll DFS(int u, int p) {
    ll s = diff[u];
    vis[u] = 1;
    FOR(i, 0, sz(g[u]) - 1) {
        int v = g[u][i].fi,
            id = g[u][i].se;

        if (v == p) continue;
        ll t = DFS(v, u);
        int x = edge[id].fi, y = edge[id].se;
        x = scc[x], y = scc[y];

        if (t > 0) ans[id] = (x == v && y == u) ? 'R' : 'L';
        else if (t < 0) ans[id] = (x == u && y == v) ? 'R' : 'L';

        s += t;
    }

    return s;
}

void giai() {
    FOR(i, 1, n) if (!tin[i]) dfs(i, -1);
    FOR(i, 1, n) if (!scc[i]) ++cnt, dfs_scc(i);

    FOR(i, 1, m) if (d[i]) {
        int u = edge[i].fi, v = edge[i].se;
        int x = scc[u], y = scc[v];
        g[x].pb({y, i});
        g[y].pb({x, i});
    }

    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        int u = scc[x], v = scc[y];
        if (u == v) continue;
        diff[u]++;
        diff[v]--;
    }

    FOR(i, 1, m) ans[i] = 'B';
    FOR(i, 1, cnt) if (!vis[i]) DFS(i, 0);
    FOR(i, 1, m) cout << ans[i];
}

mingdu {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    nhap();
    giai();

    return 0;
}

Compilation message (stderr)

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

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