제출 #550346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550346		leaked	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	12 ms	23764 KiB

oneway

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=5e5+1;

vec<array<int,3>> g[N];
int in[N],out[N],tt=1,fup[N],up[N][20];
char clr[N];
bool is(int a,int b){
    return in[a]<=in[b]&&out[a]>=out[b];
}
vec<array<int,3>> gr[N];
void dfs(int v,int p,int pr){
    in[v]=fup[v]=tt++;
    up[v][0]=pr;
    for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto &z : g[v]){
        if(z[1]==p) continue;
        if(in[z[0]]){
            umin(fup[v],in[z[0]]);
            if(in[z[0]]<in[v])
                cout<<"E! "<<v<<' '<<z[0]<<endl;
            clr[z[1]]='B';
        }
        else{
//                        cout<<"E "<<v<<' '<<z[0]<<endl;

            dfs(z[0],z[1],v);
            gr[v].pb(z);
            umin(fup[v],fup[z[0]]);
//            cout<<"E "<<v<<' '<<z[0]<<' '<<in[v]<<' '<<fup[z[0]]<<endl;
            if(fup[z[0]]<=in[v])
                clr[z[1]]='B';
            else
                clr[z[1]]='.';
        }
    }
    out[v]=tt-1;
}
int dp[N][2];
string fck="LR";
void dfs2(int v){
    for(auto &z : gr[v]){
        dfs2(z[0]);
        for(int t=0;t<2;t++)
            dp[v][t]+=dp[z[0]][t];
//        cout<<dp[z[0]][0]<<' '<<
        if(dp[z[0]][0] || dp[z[0]][1]){
            if(clr[z[1]]=='B') continue;
            if(dp[z[0]][0])
                clr[z[1]]=fck[0^z[2]^1];
            else
                clr[z[1]]=fck[1^z[2]^1];
        }
        else clr[z[1]]='B';
    }
}
int lca(int a,int b){
    if(is(a,b)) return a;
    for(int i=19;i>=0;i--){
        if(!is(up[a][i],b))
            a=up[a][i];
    }
    return up[a][0];
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb({u,i,0});
        g[u].pb({v,i,1});
    }
    vec<int>roots;
    for(int i=0;i<n;i++){
        if(!in[i])
            roots.pb(i),dfs(i,-1,i);
    }
    int q;
    cin>>q;
    while(q--){
        int v,u;
        cin>>v>>u;--v;--u;
        cerr<<"WO "<<v<<' '<<u<<' '<<lca(v,u)<<endl;
        dp[v][1]++;
        dp[u][0]++;
        dp[lca(v,u)][0]--;
        dp[lca(v,u)][1]--;
    }
    for(auto &z : roots)
        dfs2(z);
    for(int i=0;i<m;i++)
        cout<<clr[i];
    return 0;
}
/*
10 10 1
6 5
5 1
1 4
2 4
2 10
3 1
3 8
9 8
9 7
6 8
3 9 8

*/

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