Submission #449015

#	Time	Username	Problem	Language	Result	Execution time	Memory
449015		ak2006	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	171 ms	25860 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int n = 1e5 + 5,m,cmp,TIMER;
vvi adj(n),graph(n);
vb ins(n);
vi dfs_time(n),dfs_low(n),num(n),scc(n),dist(n);
stack<int>s;
void dfs(int u,int p)
{
    dfs_low[u] = dfs_time[u] = ++TIMER;
    s.push(u);
    ins[u] = 1;
    for (int v:adj[u]){
        if (v == p){p = -1;continue;}
        if (!dfs_time[v]){
            dfs(v,u);
            dfs_low[u] = min(dfs_low[u],dfs_low[v]);
            continue;
        }
        if (ins[v])
            dfs_low[u] = min(dfs_low[u],dfs_time[v]);
    }
    if (dfs_time[u] == dfs_low[u]){
        int v = -1;
        cmp++;
        while (v != u){
            v = s.top();
            scc[v] = cmp;
            ins[v] = 0;
            s.pop();   
        }
    }
}   
void tree(int u,int p)
{
    for (int v:graph[u]){
        if (v == p)continue;
        dist[v] = dist[u] + 1;
        tree(v,u);
        num[u] += num[v];
    }
    //cout<<u<<" "<<num[u]<<endl;
}
int main()
{
    setIO();
    cin>>n>>m;
    vvi edges;
    while (m--){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v),adj[v].pb(u);
        edges.pb({u,v});
    }
    for (int i = 1;i<=n;i++)
        if (!dfs_time[i])dfs(i,-1);
    int q;
    cin>>q;
    while (q--){
        int u,v;
        cin>>u>>v;
        num[scc[u]]++,num[scc[v]]--;
        //cout<<"HERE "<<scc[u]<<" "<<scc[v]<<" "<<num[scc[u]]<<" "<<num[scc[v]]<<endl;
    }
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (u != v)
        graph[u].pb(v),graph[v].pb(u);
    }
    for (int i = 1;i<=cmp;i++)
        if (!dist[i])tree(i,-1);
    
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (dist[u] > dist[v])swap(u,v);
        //cout<<u<<" "<<v<<" "<<num[u]<<" "<<num[v]<<endl;
    }
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (u == v){cout<<"B";continue;}
        
        if (dist[u] > dist[v]){
            if (num[u] > 0)cout<<"R";
            else if (num[u] == 0)cout<<"B";
            else cout<<"L";
        }
        else{
            if (num[v] > 0)cout<<"L";
            else if (num[v] == 0)cout<<"B";
            else cout<<"R";
        }
    }
    return 0;
}

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