Submission #349298

#	Time	Username	Problem	Language	Result	Execution time	Memory
349298		doowey	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	102 ms	17244 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pii> T[N];
int tin[N];
int tout[N];
int low[N];
int u[N], v[N];
bool bridge[N];
int ti;
bool use[N];

void dfs(int u, int pp){
    ti++;
    tin[u]=ti;
    low[u]=tin[u];
    for(auto x : T[u]){
        if(tin[x.fi] == 0){
            dfs(x.fi,x.se);
            use[x.se]=true;
            low[u]=min(low[u],low[x.fi]);
            if(tin[u] < low[x.fi]){
                bridge[x.se]=true;
            }
        }
        else if(x.se != pp){
            low[u]=min(low[u],tin[x.fi]);
        }
    }
    tout[u]=ti;
}


char sol[N];

void setd(int xi, int yi, int id){
    if(xi == u[id]){
        sol[id]='R';
    }
    else{
        sol[id]='L';
    }
}

int in_low[N], in_high[N];
int out_low[N], out_high[N];

void dfs2(int u, int pi){
    for(auto x : T[u]){
        if(use[x.se] && x.se != pi){
            dfs2(x.fi,x.se);
            in_low[u]=min(in_low[u],in_low[x.fi]);
            out_low[u]=min(out_low[u],out_low[x.fi]);
            in_high[u]=max(in_high[u],in_high[x.fi]);
            out_high[u]=max(out_high[u],out_high[x.fi]);
            if(bridge[x.se]){
                if(in_low[x.fi] < tin[x.fi] || in_high[x.fi] > tout[x.fi]){
                    setd(u,x.fi,x.se);
                }
                else if(out_low[x.fi] < tin[x.fi] || out_high[x.fi] > tout[x.fi]){
                    setd(x.fi,u,x.se);
                }
            }
        }
    }
}

int main(){
    fastIO;
    int n, m, p;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ ){
        cin >> u[i] >> v[i];
        T[u[i]].push_back(mp(v[i],i));
        T[v[i]].push_back(mp(u[i],i));
    }
    vector<int> ord;
    for(int i = 1; i <= n; i ++ ){
        if(tin[i] == 0){
            ord.push_back(i);
            dfs(i,-1);
        }
    }
    for(int i = 1; i <= m; i ++ ){
        sol[i]='B';
    }
    for(int i = 1; i <= n; i ++ ){
        in_low[i]=n+1;
        out_low[i]=n+1;
    }
    cin >> p;
    int xi, yi;
    for(int i = 1; i <= p ; i ++ ){
        cin >> xi >> yi;
        in_low[yi]=min(in_low[yi],tin[xi]);
        out_low[xi]=min(out_low[xi],tin[yi]);
        in_high[yi]=max(in_high[yi],tin[xi]);
        out_high[xi]=max(out_high[xi],tin[yi]);
    }
    for(auto x : ord )
        dfs2(x,-1);
    for(int i = 1; i <= m ; i ++ ){
        cout << sol[i];
    }
    cout << "\n";
    return 0;
}

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