Submission #595175

#	Time	Username	Problem	Language	Result	Execution time	Memory
595175		OttoTheDino	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	295 ms	33784 KiB

oneway

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 1e5, C = 30;
vii adj[mx+1];
vi reach[mx+1];
int tp[mx+1], par[mx+1][C+1], dep[mx+1], cyc[mx+1], delta[mx+1], done[mx+1]; 
ii edg[mx+1];

int go_up (int x, int l) {
    rep (i,0,C) {
        if (l%2) x = par[x][i];
        l /= 2;
    }
    return x;
}

int lca (int a, int b) {
    if (dep[a]<dep[b]) swap(a,b);
    int dif = dep[a]-dep[b];
    a = go_up (a, dif);

    if (a==b) return a;

    rrep (i, C, 0) {
        if (par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }

    return par[a][0];
}


void dfs (int u) {
    for (ii ve : adj[u]) {
        int v = ve.fi;
        if (!par[v][0]) {
            dep[v] = dep[u]+1;
            par[v][0] = u;
            dfs (v);
        }
    }
}

ii dfs2 (int u, int le) {
    done[u] = 1;
    int c = 0, d = 0;
    for (ii ve : adj[u]) {
        int v = ve.fi, e = ve.se;

        if (e==le) continue;

        if (done[v]) {
            if (dep[v]<dep[u]) {
                c++;
                cyc[v]++;
            }
            continue;
        }

        ii res = dfs2 (v, e);

        if (!res.fi && res.se) {
            if ((res.se>0 && edg[e].fi!=u) || (res.se<0 && edg[e].fi==u)) tp[e] = 2;
            else tp[e] = 1;
        }
        c += res.fi;
        d += res.se;
    }

    c -= cyc[u];
    d -= delta[u];

    for (int v : reach[u]) {
        int p = lca(abs(v),u);
        if (p!=u) {
            d += 1-2*(v<0);
            delta[p] += 1-2*(v<0);
        }
    }

    return {c,d};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;

    rep (i,1,m) {
        int a, b; cin >> a >> b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
        edg[i] = {a,b};
    }

    int p; cin >> p;

    rep (i,1,p) {
        int x, y; cin >> x >> y;
        reach[x].pb(y);
        reach[y].pb(-x);
    }

    dep[1] = 1;

    rep (i,1,n) {
        if (!par[i][0]) {
            par[i][0] = i;
            dfs (i);
        }
    }

    rep (i,1,C)
        rep (j,1,n)
            par[j][i] = par[par[j][i-1]][i-1];

    rep (i,1,n) {
        if (!done[i]){
        dfs2 (i,-1);
        }
    }

    rep (i,1,m) cout << "BLR"[tp[i]];
    cout << "\n";

    return 0;
}

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