제출 #1027343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027343		ojnewbie111	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3043 ms	13388 KiB

oneway

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,m,p;
struct node{
    int to,num,direct;
};
vector<node>g[N];
vector<pi>edge;
bool vis[N];
int num[N],low[N],tdfs=0;
bool bridge[N],joint[N];
void dfs(int u,int p)
{
    low[u]=num[u]=++tdfs;
    vis[u]=1;
    bool p_skip=0;
    for (node &e:g[u]) {
        int v=e.to,pos=e.num;
        if (v==p && !p_skip) {p_skip=1; continue;}
        if (!num[v]) {
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>num[u]) bridge[pos]=1;
            //if (pos==447) cout<<low[v]<<" "<<num[v]<<endl;
        }
        else low[u]=min(low[u],num[v]);
    }
}
int ans[N];
node par[N];
vector<pi>require;
void dfs2(int u,int p,int stop)
{
    vis[u]=1;
    if (u==stop) return;
    for (node &e:g[u]) {
        int v=e.to,pos=e.num;
        if (vis[v]) continue;
        par[v]={u,pos,e.direct};
        dfs2(v,u,stop);
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=m;i++) {int a,b; cin>>a>>b; edge.push_back({a,b}); g[a].push_back({b,i,0}); g[b].push_back({a,i,1});}
    cin>>p;
    for (int i=1;i<=p;i++) {int x,y; cin>>x>>y; require.push_back({x,y});}
    for (int i=1;i<=n;i++) if (!vis[i]) dfs(i,i);
    //cout<<bridge[447]<<endl;
    for (int i=1;i<=p;i++) {
        fill_n(vis,n+1,0);
        for (int i=1;i<=n;i++) par[i]={0,0,0};
        dfs2(require[i-1].fi,require[i-1].fi,require[i-1].se);
        int t=require[i-1].se;
        //cout<<t<<endl;
        while (t!=require[i-1].fi) {
            int pos=par[t].num;
            if (bridge[pos])
                ans[pos]=par[t].direct ? 2 : 1; //cout<<t<<" "<<par[t].to<<" "<<pos<<" "<<bridge[pos]<<endl;
            t=par[t].to;
            //cout<<t<<endl;
        }
        //cout<<endl;
        //cout<<endl;
    }
    for (int i=1;i<=m;i++) if (ans[i]==0) cout<<"B"; else if (ans[i]==1) cout<<"R"; else cout<<"L";
}

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