Submission #468708

#	Time	Username	Problem	Language	Result	Execution time	Memory
468708		wdjpng	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	204 KiB

oneway

#include <bits/stdc++.h>
//#define double double
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;

struct edge{
    int b=1;
    int rev=0;
    int i=1;
};

int t,m;
vector<vector<edge>>E;
vector<int>pre, low;
vector<vector<int>>low_constrained;
vector<vector<vector<int>>>rests;
vector<int>orient;

int counter=0;
void dfs(int v, int i)
{
    pre[v]=counter++;
    low[v]=pre[v];
    rep(i,2) low_constrained[i][v] = pre[v];

    for(edge w : E[v])
    {
        if(w.i==i) continue;
        if(pre[w.b]!=-1) {low[v]=min(low[w.b], low[v]); continue;}
        dfs(w.b, w.i);
        if(low[w.b]==pre[w.b]) // edge w is a bridge
        {
            rep(i,2) {
                if(low_constrained[i][w.b]<=pre[v]) 
                    orient[w.i] = (w.rev+i+1) % 2;
            }
        }
        low[v]=min(low[w.b], low[v]);
        rep(i,2) low_constrained[i][v] = min(low_constrained[i][v], low_constrained[i][w.b]);
    }

    rep(i,2)
    {
        for(int w : rests[i][v])
        {
            low_constrained[i][v] = min(low_constrained[i][w], low_constrained[i][v]);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m;
    cin>>n>>m;

    E.resize(n);
    rep(i, m)
    {
        int a,b;
        cin>>a>>b;
        a--; b--;
        E[a].push_back({b, 0, i});
        E[b].push_back({a, 1, i});
    }

    pre.assign(n, -1);
    low.assign(n, -1);
    low_constrained.assign(2, vector<int>(n, 1e16));
    orient.assign(m, 2);
    rests.assign(2, vector<vector<int>>(n));

    int p;
    cin>>p;
    rep(i,p)
    {
        int a,b;
        cin>>a>>b;
        a--; b--;
        rests[0][a].push_back(b);
        rests[1][b].push_back(a);
    }

    rep(i, n)
    {
        if(pre[i]!=-1||E[i].size()>1) continue;
        dfs(i, -1);
    }

    for(int o : orient)
    {
        if(o==0) cout<<"R";
        if(o==1) cout<<"L";
        if(o==2) cout<<"B";
    }
    cout<<"\n";
}

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