Submission #468685

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

oneway

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

vector<int> pre;
vector<int> low;
vector<vector<int>> graph;
map<pair<int,int>,int> edges;
vector<pair<int,int>> indedge;
vector<bool> bridges;
int tim;

void dfs1(int v, int p=-1){
    pre[v]=tim++;
    low[v]=pre[v];
    for(auto u:graph[v]){
        if(u==p)continue;
        if(pre[u]==-1){
            dfs1(u,v);
            low[v]=min(low[v],low[u]);
            if(low[u]>pre[v]){
                int ind=edges[{v,u}];
                bridges[ind]=true;
            }
        }else{
            low[v]=min(low[u], low[v]);
        }
    }
}

string s;
vector<bool> visited;
bool dfs2(int v, int t){
    if(visited[v]) return false;
    visited[v]=true;
    if(v==t)return true;
    for(auto u:graph[v]){
        if(dfs2(u,t)){
            int in=edges[{v,u}];
            if(bridges[in]){
                if(v==indedge[in].first){
                    s[in]='R';
                }else{
                    s[in]='L';
                }
            }
            return true;
        }
    }
    return false;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    tim=0;
    int n,m;
    cin>>n>>m;

    pre.resize(n,-1);
    low.resize(n,-1);
    bridges.resize(m);
    graph.resize(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        indedge.push_back({a,b});
        edges[{a,b}]=i;
        edges[{b,a}]=i;
    }

    dfs1(0);

    s.resize(m,'B');
    int p;
    cin>>p;
    for(int i=0;i<p;i++){
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        visited.assign(n,false);
        bool b=dfs2(x,y);
    }
    cout<<s<<"\n";
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:89:14: warning: unused variable 'b' [-Wunused-variable]
   89 |         bool b=dfs2(x,y);
      |              ^

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