Submission #347193

#	Time	Username	Problem	Language	Result	Execution time	Memory
347193		Noran	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3074 ms	20972 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 19;
const int SQ = 400;

int n, m;

int a[maxn], b[maxn];

int mark[maxn], low[maxn], h[maxn];
bool dfn[maxn];

vector<pii> adj[maxn];

int par[maxn][mlog];
int f[maxn];

int parID[maxn];
int res[maxn];

int cnt = 0;

int get(int v) { return (f[v] == v ? v : get(f[v])); }

void dfs(int v)
{
    mark[v] = low[v] = ++cnt;
    for(pii Ed : adj[v])
    {
        int u = Ed.F;
        int ind = Ed.S;

        if(!mark[u])
        {
            h[u] = h[v] + 1;
            par[u][0] = v;
            parID[u] = ind;
            dfs(u);

            low[v] = min(low[u], low[v]);

            if(low[u] > mark[v]) dfn[u] = 1;
        }
        else
        {
            if(par[u][0] == v) dfn[u] = 0;
            if(u != par[v][0]) low[v] = min(low[u], low[v]);
        }
    }
}

void prep()
{
    for(int j=1;j<mlog;j++)
        for(int i=1;i<=n;i++)
            par[i][j] = par[par[i][j-1]][j-1];
}

int lca(int u,int v)
{
    if(h[u] > h[v])
        swap(u, v);

    for(int i=mlog-1;i >= 0;i--)
        if(h[par[v][i]] >= h[u])
            v = par[v][i];

    if(u == v) return v;

    for(int i=mlog-1;i>=0;i--)
    {
        if(par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[v][0];
}

int main()
{
    FAST;

    cin >> n >> m;

    for(int i=1;i<=m;i++)
    {
        cin >> a[i] >> b[i];

        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    for(int i=1;i<=n;i++) if(!mark[i]) dfs(i);

    prep();

    for(int i=1;i<=n;i++) f[i] = i;

    int p;
    cin >> p;

    while(p--)
    {
        int u, v;
        cin >> u >> v;

        int lpa = lca(u, v);

        u = get(u);
        while(h[u] > h[lpa])
        {
            if(dfn[u]) res[parID[u]] = -1;
            f[u] = par[u][0];
            u = get(u);
        }

        v = get(v);
        while(h[v] > h[lpa])
        {
            if(dfn[v]) res[parID[v]] = 1;
            f[v] = par[v][0];
            v = get(v);
        }
    }

    for(int i=1;i<=n;i++)
        if(dfn[i] && b[parID[i]] != i)
            res[parID[i]] *= -1;

    for(int i=1;i<=m;i++)
    {
        if(res[i] == 1) cout << "R";
        if(res[i] == -1) cout << "L";
        if(res[i] == 0) cout << "B";
    }

    return 0;
}

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