oj.uz

답안 #856447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856447 2023-10-03T13:52:36 Z 8pete8 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 4 ms 18008 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
//#define int long long
const int mxn=2*1e5,mod=29947,lg=30;
vector<pii>adj[mxn+10],e,adj2[mxn+10];
int low[mxn+10],g[mxn+10],id[mxn+10];
int up[mxn+10][lg+10],h[mxn+10],ans[mxn+10];
pii info[mxn+10];
stack<int>st;
bitset<mxn+10>on;
int t=0,cnt=0;
void tarjan(int cur,int pa){
    id[cur]=low[cur]=++t;
    on[cur]=true;
    st.p(cur);
    for(auto i:adj[cur]){
        if(i.f==pa)continue;
        if(!id[i.f])tarjan(i.f,cur),low[cur]=min(low[cur],low[i.f]);
        else if(on[i.f])low[cur]=min(low[cur],low[i.f]);
    }
    if(low[cur]==id[cur]){
        cnt++;
        while(st.top()!=cur){
            g[st.top()]=cnt;
            on[st.top()]=false;
            st.pop();
        }
        on[st.top()]=false;
        g[st.top()]=cnt;
        st.pop();
    }
}
void dfs(int cur,int pa){
    if(on[cur])return;
    on[cur]=true;
    for(auto i:adj2[cur]){
        if(i.f==pa)continue;
        up[i.f][0]=cur;
        h[i.f]=h[cur]+1;
        dfs(i.f,cur);
    }
}
int lca(int a,int b){
    if(h[a]<h[b])swap(a,b);
    int k=h[a]-h[b];
    for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
    if(a==b)return a;
    for(int i=lg;i>=0;i--){
        if(up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}
//ans 1=right,2 left
void push(int cur,int pa){
    if(on[cur])return;
    on[cur]=true;
    for(auto i:adj2[cur]){
        if(i.f==pa)continue;
        push(i.f,cur);
        if(info[i.f].f){
            if(info[i.f].f!=cur&&(!info[cur].f||h[info[i.f].f]<h[info[cur].f]))info[cur]=info[i.f];
            if(info[i.f].s){
                if(g[e[i.s].f]==i.f)ans[i.s]=1;
                else ans[i.s]=2;
            }
            else{
                if(g[e[i.s].f]==cur)ans[i.s]=1;
                else ans[i.s]=2;
            }
        }
    }
}
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        e.pb({u,v});
        adj[v].pb({u,i});
        adj[u].pb({v,i});
    }
    for(int i=1;i<=n;i++)if(!g[i])tarjan(i,-1);
    for(int i=1;i<=n;i++)for(auto j:adj[i])if(g[j.f]!=g[i])adj2[g[i]].pb({g[j.f],j.s});
    on.reset();
    for(int i=1;i<=cnt;i++)if(!on[i])dfs(i,-1);
    for(int j=1;j<=lg;j++)for(int i=1;i<=cnt;i++)up[i][j]=up[up[i][j-1]][j-1];
    int k;cin>>k;
    for(int i=0;i<k;i++){
        int u,v;cin>>u>>v;
        int a=u,b=v;
        u=g[u],v=g[v];
        if(u==v)continue;
        int node=lca(u,v);
        if(u!=node&&(info[u].f==0||h[info[u].f]>h[node]))info[u].f=node;
        if(v!=node&&(info[v].f==0||h[info[v].f]>h[node]))info[v].f=node;
        if(u!=node)info[u].s=1;
    }
    on.reset();
    for(int i=1;i<=cnt;i++)if(!on[i])push(i,-1);
    for(int i=0;i<m;i++){
        if(ans[i])cout<<((ans[i]==1)?"R":"L");
        else cout<<"B";
    }
}

Compilation message

oneway.cpp: In function 'int32_t main()':
oneway.cpp:120:13: warning: unused variable 'a' [-Wunused-variable]
  120 |         int a=u,b=v;
      |             ^
oneway.cpp:120:17: warning: unused variable 'b' [-Wunused-variable]
  120 |         int a=u,b=v;
      |                 ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 4 ms 17864 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Incorrect 3 ms 17752 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 4 ms 17864 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Incorrect 3 ms 17752 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 4 ms 17864 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Incorrect 3 ms 17752 KB Output isn't correct
10 Halted 0 ms 0 KB -