Submission #469090

#	Time	Username	Problem	Language	Result	Execution time	Memory
469090		wdjpng	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	322 ms	52440 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]);
        }
    }
}

int c = 0;
vector<int>preord, postord;
vector<vector<int>>up;


bool isanc(int w, int v)
{
    return preord[w]>=preord[v]&&postord[w]<=postord[v];
}

int lca(int a, int b)
{
    if(isanc(a,b)) return b;
    if(isanc(b,a)) return a;
    for(int i = 19; i>= 0; i--) if(!isanc(a, up[b][i])) b = up[b][i];
    return up[b][0];
}

vector<bool>vis(1e5+1);
void dfs2(int v, int p)
{
    vis[v]=true;
    preord[v]=c++;
    up[v][0]=p;
    for(auto w : E[v])
    {
        if(!vis[w.b]) dfs2(w.b,v);
    }
    postord[v]=c++;
}

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));
    up.assign(n, vector<int>(20));
    preord.assign(n,-1);
    postord.assign(n,-2);

    dfs2(0, 0);
    for(int i = 1; i < 20;i++)
    {
        rep(j,n) up[j][i] = up[up[j][i-1]][i-1];
    }
    int p;
    cin>>p;
    rep(i,p)
    {
        int a,b;
        cin>>a>>b;
        a--; b--;
        int c = lca(a,b);
        rests[0][a].push_back(c);
        rests[0][c].push_back(b);
        
        rests[1][b].push_back(c);
        rests[1][c].push_back(a);
    }

    rep(i, n)
    {
        if(pre[i]!=-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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40