Submission #466327

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

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif

#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define pm make_pair
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++) 
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll MOD=1e9+7;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }

template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}        
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}

ll getbit(ll number, ll index){return (number & (1<<index))<<index;}

struct LCA{
    vl enter, exit;
    vvl jump, graph;
    ll n;

    vl seen;
    ll timer;
    LCA(vvl _graph, ll root=0){
        graph=_graph;
        n=graph.size();
        enter.resize(n);
        exit.resize(n);
        jump.resize(n);
        timer=0;
        seen.resize(n,0);
        dfs(root);
        jump[root].push_back(root);
        ll cn=n,i=0;
        while(cn){
            cn>>=1;
            REP(j,n) jump[j].push_back(jump[jump[j][i]][i]);
            i++;
        }
    }
    void dfs(ll i){
        enter[i]=timer;
        timer++;
        seen[i]=1;
        EACH(j,graph[i]){
            if(!seen[j]){
                dfs(j);
                jump[j].push_back(i);
            }
        }
        exit[i]=timer;
        timer++;
    }
    bool ispredcessor(ll parent, ll child){
        return enter[parent]<=enter[child] && exit[parent]>=exit[child];
    }
    ll solve(ll a, ll b){
        if(ispredcessor(a,b)) return a;
        if(ispredcessor(b,a)) return b;
        for(ll i=jump[a].size()-1; i>=0; i--){
            if(!ispredcessor(jump[a][i],b)) a=jump[a][i];
        }
        return jump[a][0];
    }
    ll operator()(ll a, ll b){
        return solve(a,b);
    }
};

vector<vector<pll>> g;
vvl used;
vl res, top, t, te, from, to;
vector<bool> s;
ll n,m;
vpll edges;

ll cnt=0;

bool ispredcessor(int a, int b){return t[a]<=t[b] && te[a]>=te[b];}

void dfs(int u, int parent=-1){
    t[u]=cnt++;
    s[u]=1;
    EACH(i,g[u]){
        if(i.ff==parent) parent=-1;
        else if(!s[i.ff]){
            dfs(i.ff,u);
            if(t[top[i.ff]]<=t[u]){
                res[i.ss]=2;
            }
            if(t[top[i.ff]]<=t[top[u]]){
                top[u]=top[i.ff];
            }
            used[u].pb(i.ff);
            used[i.ff].pb(u);
        }
        else{
            res[i.ss]=2;
            if(t[i.ff]<=t[top[u]]){
                top[u]=i.ff;
            }
        }
    }
    te[u]=cnt++;
}

void dfs2(int u, LCA& lca){
    s[u]=1;
    EACH(i,g[u]){
        if(!s[i.ff]){
            dfs2(i.ff, lca);
            if(ispredcessor(lca.solve(from[i.ff],i.ff),from[u])) from[u]=lca.solve(from[i.ff],i.ff);
            if(ispredcessor(lca.solve(to[i.ff],i.ff),to[u])) to[u]=lca.solve(to[i.ff],i.ff);

            if(!ispredcessor(i.ff,from[i.ff]) && res[i.ss]==-1){
                res[i.ss]=(make_pair(1+from[i.ff],i.ff+1)==edges[i.ss]);
            }
            else if(!ispredcessor(i.ff,to[i.ff]) && res[i.ss]==-1){
                res[i.ss]=(make_pair(1+i.ff,to[i.ff]+1)==edges[i.ss]);
            }
            else res[i.ss]=2;
        }
    }
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>n>>m;

    edges.resize(m);
    g.resize(n);
    used.resize(n);

    cin>>edges;

    REP(i,m){
        g[edges[i].ff-1].pb({edges[i].ss-1,i});
        g[edges[i].ss-1].pb({edges[i].ff-1,i});
    }

    
    s.resize(n,0);
    res.resize(m,-1);
    t.resize(n);
    te.resize(n);
    REP(i,n) top.pb(i);
    REP(i,n) from.pb(i);
    REP(i,n) to.pb(i);

    dfs(0);
    
    LCA lca(used);
    ll p;
    cin>>p;
    REP(i,p){
        ll f,t;
        cin>>f>>t;
        f--;t--;
        if(ispredcessor(lca.solve(f,t),from[f])) from[f]=lca.solve(f,t);
        if(ispredcessor(lca.solve(f,t),to[t])) to[t]=lca.solve(f,t);
    }


    s.assign(n,0);
    dfs2(0,lca);

    EACH(i,res){
        cout<<"RLB"[i];
    }
    cout<<endl;

    return 0;
}

Compilation message (stderr)

oneway.cpp: In member function 'void LCA::dfs(ll)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   18 | #define EACH(i,c) for(auto (i):c)
      |                            ^
oneway.cpp:100:9: note: in expansion of macro 'EACH'
  100 |         EACH(j,graph[i]){
      |         ^~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define EACH(i,c) for(auto (i):c)
      |                            ^
oneway.cpp:139:5: note: in expansion of macro 'EACH'
  139 |     EACH(i,g[u]){
      |     ^~~~
oneway.cpp: In function 'void dfs2(int, LCA&)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define EACH(i,c) for(auto (i):c)
      |                            ^
oneway.cpp:164:5: note: in expansion of macro 'EACH'
  164 |     EACH(i,g[u]){
      |     ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define EACH(i,c) for(auto (i):c)
      |                            ^
oneway.cpp:225:5: note: in expansion of macro 'EACH'
  225 |     EACH(i,res){
      |     ^~~~

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