Submission #213338

#	Time	Username	Problem	Language	Result	Execution time	Memory
213338		Blerargh	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	326 ms	53600 KiB

oneway

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;

#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define ROF(i, a, b) for(int i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v);
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort((x).begin(), (x).end())
#define CMPSORT(x, cp) sort((x).begin(), (x).end(), cp)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front

#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';

const ll MOD = 1e9+7; //998244353
const ll MAXN = 1e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);

ll n, m, p, a, b, idx;
ll ind[MAXN], low[MAXN], cycleID[MAXN], cyclecnt=0;
vector<ll> in_stack;
vector<tuple<ll, ll, char> > adjlist[MAXN]; //nextnode, id, left or right
vector<tuple<ll, ll, char> > cact[MAXN];
char edges[MAXN];

void dfs(ll u, ll idd){
    low[u] = ind[u] = ++idx;
    in_stack.pb(u);
    for (auto edge : adjlist[u]){
        ll v = get<0>(edge);
        if (ind[v] == 0){ //node not visited
            dfs(v, get<1>(edge));
            low[u] = min(low[u], low[v]);

            if (low[v] > ind[u]) edges[get<1>(edge)] = '-'; //is bridge
            
        } else if (get<1>(edge) != idd) { //back edge to v
            low[u] = min(low[u], ind[v]);
        }
    }

    if (ind[u] == low[u]){
        cyclecnt++;
        while (1){
            cycleID[in_stack.bk()] = cyclecnt;
            if (in_stack.bk() == u) break;
            in_stack.ppb();
        }
        in_stack.ppb();
    }
}

ll visited[MAXN], depth[MAXN];
vector<tuple<ll, ll, char> > prevedge(MAXN);
ll par[18][MAXN];

void lcainit(ll u, ll dep){
    visited[u] = 1;
    depth[u] = dep;
    for (auto edge : cact[u]){
        ll v = get<0>(edge);
        if (!visited[v]){
            par[0][v] = u;
            prevedge[v] = edge;
            lcainit(v, dep+1);
        }
    }
}

void parinit(){
    FOR(i,1,17){
        FOR(j,1,n){
            par[i][j] = par[i-1][par[i-1][j]];
        }
    }
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);
    ll diff = depth[a] - depth[b];

    ll cnt=0;
    while (diff){
        if (diff&1) a = par[cnt][a];
        cnt++;
        diff>>=1;
    }

    if (a==b) return a;

    ROF(i,17,0){
        if (par[i][a] != par[i][b]){
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

int main(){
    FAST
    cin >> n >> m;
    FOR(i,1,m){
        cin >> a >> b;
        adjlist[a].eb(b,i,'R');
        adjlist[b].eb(a,i,'L');
    }

    MEM(edges, 'B');

    FOR(i,1,n){
        if (ind[i] == 0){
            dfs(i, -1);
        }
    }

    FOR(i,1,n){
        ll sz = adjlist[i].size()-1;
        FOR(j,0,sz){
            ll u = i;
            ll v, idd;
            char dir;
            tie(v,idd,dir) = adjlist[i][j];

            if (cycleID[u] != cycleID[v]) cact[cycleID[u]].eb(cycleID[v],idd,dir);
        }
    }

    FOR(i,1,cyclecnt){
        if (!visited[i]) {
            par[0][i] = i;
            lcainit(i,0);
        }
    }
    
    parinit();

    cin >> p;

    vector<tuple<ll,ll,ll,ll> > pairs; // depth, u, v, ancestor
    FOR(i,1,p){
        cin >> a >> b;
        a = cycleID[a];
        b = cycleID[b];
        ll anc = lca(a,b);
        pairs.eb(depth[anc], a, anc, anc);
        pairs.eb(depth[anc], anc, b, anc);
    }
    sort(ALL(pairs));

    for (auto pr : pairs){
        ll u = get<1>(pr);
        ll v = get<2>(pr);

        ll ancestor = get<3>(pr);

        while (u != ancestor){
            ll idd = get<1>(prevedge[u]);
            ll dirc = get<2>(prevedge[u]);

            if (edges[idd] != '-') break;
            else {
                if (dirc == 'R') edges[idd] = 'L';
                else edges[idd] = 'R';
                u = par[0][u];
            }
        }

        while (v != ancestor){
            ll idd = get<1>(prevedge[v]);
            ll dirc = get<2>(prevedge[v]);

            if (edges[idd] != '-') break;
            else {
                if (dirc == 'R') edges[idd] = 'R';
                else edges[idd] = 'L';
                v = par[0][v];
            }
        }
    }

    FOR(i,1,m){
        if (edges[i] == '-') cout << "B";
        else cout << edges[i];
    }
}

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